Succinct dynamic data structures

Abstract. We develop succinct data structures to represent (i) a se-quence of values to support partial sum and select queries and update (changing values) and (ii) a dynamic array consisting of a sequence of elements which supports insertion, deletion and access of an element at any given index. For the partial sums problem on n non-negative integers of k bits each, we support update operations in O(b) time and sum in O(logb n) time, for any parameter b, lg n / lg lg n ≤ b ≤ n for any fixed positive < 1. The space used is kn+o(kn) bits and the time bounds are optimal. When b = lg n / lg lg n or k = 1 (i.e., when we are dealing with a bit-vector), we can also support the select operation in the same time as the sum operation, but the update time becomes amortised. For the dynamic array problem, we give two structures both using o(n) bits of extra space where n is the number of elements in the array: one supports lookup in constant worst case time and updates in O(n) worst case time, and the other supports all operations in O(lgn / lg lg n) amortized time. The time bound of both these structures are optimal.