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..σ] in time O(lg n/lg lg n), which is optimal. The time is worst-case for the queries and amortized for the updates. This complexity is better than the best previous ones by a Θ(1 + lg σ/lg lg n) factor. Our structure uses nH0(S) + O(n + σ(lg σ + lg1+e n)) bits, where H0(S) is the zero-order entropy of S and 0 < e < 1 is any constant. This space redundancy over nH0(S) is also better, almost always, than that of the best previous dynamic structures, o(n lg σ) + O(σ(lg σ+lg n)). We can also handle general alphabets in optimal time, which has been an open problem in dynamic sequence representations.
['Gonzalo Navarro', 'Yakov Nekrich']
Optimal dynamic sequence representations