Succinct data structures for Searchable Partial Sums

Abstract

The Searchable Partial Sums is a data structure problem that maintains a sequence of n non-negative k-bit integers; in addition, it allows us to modify the entries by the update operation, while supporting two types of queries: sum and search. Recently, researchers focus on the succinct representation of the data structure in kn + o(kn) bits. They study the tradeoff in time between the query and the update operations, under the word RAM with word size O(lg U) bits. For the special case where k = 1 (which is known as Dynamic Bit Vector problem), Raman et al. showed that both queries can be supported in O(logb n) time, while update requires O(b) amortized time for any b with lg n/lg lg n ≤ b ≤ n. This paper generalizes the study and shows that even for k = O(lg lg n), both query and update operations can be maintained using the same time complexities. Also, the time for update becomes worst-case time. For the general case when k = O(lg U), we show a lower bound of Ω (√lg n/lg lg n) time for the search query. On the other hand, we propose a data structure that supports sum in O(logb n) time, search in O(τ logb cn) time, and update in O(b) time, where τ denotes the value of min {lg lg n lg lg U/lg lg lg U, √lg n/lg lg n}. When b = n∈, our data structure achieves optimal time bounds. This paper also extends the Searchable Partial Sums with insert and delete operations, and provides succinct data structure for some cases. © Springer-Verlag Berlin Heidelberg 2003.