June 22, 2025
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.
Succinct
Browse posts by tag
Browse posts by tag
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.