Optimal Dynamic Sequence Representations
Gonzalo Navarro, Yakov Nekrich · SIAM Journal on Computing · 2014
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+\log\sigma/\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.