Optimal Dynamic Sequence Representations
Gonzalo Navarro and Yakov Nekrich
We describe a data structure that supports access, rank and select queries,
as well as symbol insertions and deletions, on a string S[1,n] over
alphabet [1..s] in time O(lg n / lglg n), which is optimal even
on binary sequences and in the amortized sense. Our time is worst-case for the
queries and amortized for the updates. This complexity is better than the best
previous ones by a Theta(1 + lg s / lglg n) factor.
We also design a variant where times are worst-case, yet rank and updates
take O(lg n) time.
Our structure uses nH_0(S) + o(n lg s) + O(s lg n)
bits, where H_0(S) is the zero-order entropy of S.
Finally, we pursue various extensions and applications of the