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