Optimal Dynamic Sequence Representations

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