Rank-Select

Succinct Bit Vectors and Rank/Select

A bit vector with O(1) rank and O(log n) select using only n + o(n) bits of space. The auxiliary index is asymptotically negligible while enabling constant-time queries.