FIX to Fully-Functional Succinct Trees

Level: Serious

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 [6] and mixing it with our structure.

A hopefully correct and complete description can be found in arXiv. There we also describe, for example, how to deamortize splits due to insertions and deletions.