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 result.