Tag
rank-and-select
- May 1, 2026 Bitset Representation and Word-Level Rank and Select How a bitvector is stored as words, how popcount turns a prefix count into a handful of instructions, and what the two-level directories for rank and select cost in bits per element. data structures
- Jul 15, 2025 Wavelet Trees and Range Queries on Sequences How recursive bitvector partitioning answers range counting, quantile, and rank queries on a static sequence, and why the space is n log σ bits rather than an index per value. data structures
- Jun 9, 2024 Balanced Parentheses and Succinct Tree Navigation How a tree becomes a 2n-bit parentheses string, which rank and select combinations recover the parent and subtree boundaries, and what the extra index buys. data structures
- Mar 19, 2024 Elias-Fano Encoding for Monotone Integer Sequences How splitting each value into a high and a low part turns a sorted sequence into one bitvector plus a packed array, and why this beats a plain array for prefix queries. data structures