ERRATA on Dynamic Entropy-Compressed Sequences and Full-Text Indexes
There is an error in Sec. 5.1.1, page 23. When using the circular arrays,
in order to make space for log n bits, it might be necessary to take out
2*log n bits from the next leaf, and then 3*log n bits from the next,
and so on. So the total cost is not O(f(n)+log n) but O(f(n)^2+log n).
Theorem 5 still holds by using f(n) = sqrt(log n) instead of f(n) = log n,
but the subsequent comparison with Gupta et al. is not anymore valid
(their sublinear terms are better).
Fortunately this error does not propagate any further. The central part of
the paper (block identifier encoding, which already needed f(n) = sqrt(log n))
stays untouched.
Thanks to Jakub Opuszaski, from University of Wrocaw, for pointing out this
error.