###
Optimal Dynamic Sequence Representations

####
Gonzalo Navarro and Yakov Nekrich

We describe a data structure that supports access, rank and select operations
on a dynamic string *S[1,n]* over alphabet *[1..s]* in worst-case time
*O(lg n / lglg n)*, which is optimal. Symbols can be inserted into and
deleted
from *S* in *O(lg n / lglg n)* amortized time. Those times are better than
the best previous dynamic time complexities by a *Theta(1 + lg s / lglg n)*
factor.
Our structure uses *nH_0(S) + o(n(1+H_0(S))) + O(s (lg s+lg^(1+e) n))*
bits, where *H_0(S)* is the zero-order entropy of *S* and
*0<e<1* is any
constant. This space redundancy over *nH_0(S)* is also better, almost always,
than that of the best previous dynamic structures, *o(n lg s) +
O(s (lg s+lg n))*.
We can also handle unbounded alphabets in optimal time, which has
been an open problem in dynamic sequence representations.