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