FIX to Fully-Functional Succinct Trees
The complexities we claim for dynamic trees are not all correct. We cannot
obtain O(log n / loglog n) time for all those operations. This stems from
errors in Section 7, which is only sketched in the paper but whose results
we used for Table 1. In particular, the use of n(i,j) to solve degree,
child, and child_rank is flawed. Lemma 7.2 is also wrong, yet we can recover
many of the O(log n / loglog n) claimed complexities by resorting to  and
mixing it with our structure.
A correct and complete description now appears in the journal version of the
paper, accepted in 2012 to appear in ACM TALG. There we also describe,
for example, how to deamortize splits due to insertions and deletions.