ABSTRACT:

Suppose you want to store an array A[1..n] of bits by a data structure
using as close to n bits as possible, and answer queries of the form
sum(k) = A[1]+...+A[k]. This is a staple problem in the field of
"succinct data structures."

I will prove a lower bound showing that, if we answer sum(k) queries
by probing t cells of w bits, then the space of the data structure
must be at least n + n/w^{O(t)} bits. This redundancy/time trade-off
is essentially optimal, matching my [FOCS'08] upper bound. I will
conclude with perspectives on the field of succinct data structures.