Cell-Probe Lower Bounds for Succinct Partial Sums
Mihai Pǎtraşcu, Emanuele Viola · 2009
The partial sums problem in succinct data structures asks to preprocess an array A[1.. n] of bits into a data structure using as close to n bits as possible, and answer queries of the form Rank(k) = ∑ k A[i]. The problem i=1 has been intensely studied, and features as a subroutine in a number of succinct data structures. We show that, if we answer Rank(k) queries by probing t cells of w bits, then the space of the data structure must be at least n+n/wO(t) bits. This redundancy/probe trade-off is essentially optimal: Patrascu [FOCS’08] showed how to achieve n + n / (w/t) Ω(t) bits. We also extend our lower bound to the closely related Select queries, and to the case of sparse arrays.