Abstract. We present a framework to dynamize succinct data structures, to encourage their use over non-succinct versions in a wide variety of important application areas. Our framework can dynamize most stateof-the-art succinct data structures for dictionaries, ordinal trees, labeled trees, and text collections. Of particular note is its direct application to XML indexing structures that answer subpath queries [2] . Our framework focuses on achieving information-theoretically optimal space along with near-optimal update/query bounds. As the main part of our work, we consider the following problem central to text indexing: Given a text T over an alphabet Σ, construct a compressed data structure answering the queries char (i), rank s (i), and select s(i) for a symbol s ∈ Σ. Many data structures consider these queries for static text T [5, 3, 16, 4] . We build on these results and give the best known query bounds for the dynamic version of this problem, supporting arbitrary insertions and deletions of symbols in T . Specifically, with an amortized update time of O(n ), any static succinct data structure D for T , taking t(n) time for queries, can be converted by our framework into a dynamic succinct data structure that supports rank s(i), select s(i), and char (i) queries in O(t(n) + log log n) time, for any constant > 0. When |Σ| = polylog(n), we achieve O(1) query times. Our update/query bounds are near-optimal with respect to the lower bounds from [13] .
There has been work on dynamizing this structure REF , where they achieve the same space plus o(n) bits, the query times are increased by O( 1 ǫ log log n), and the update times are O( 1 ǫ n ǫ ) amortized, for any constant 0 < ǫ < 1.
A Framework for Dynamizing Succinct Data Structures ⋆
ICALP
Computer Science