Abstract

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..sigma] in time O(log n/log log 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 + logs/log log n) factor. We also design a variant where times are worst case, yet rank and updates take O(log n) time. Our structure uses nH(0)(S) + o(n log sigma) + O(sigma log n) bits, where H-0(S) is the zero-order entropy of S. Finally, we pursue various extensions and applications of the result.