RankSelect

Rankselect refers to data structures and algorithms that support fast queries on binary sequences, most commonly bit vectors. The two fundamental operations are rank and select. Given a bit vector B of length n, rank1(i) returns the number of 1s among the first i bits (0 ≤ i ≤ n), and rank0(i) returns the number of 0s in the same prefix, i.e., i − rank1(i). The select operations locate the position of the i-th 1 or i-th 0. For example, select1(j) returns the index of the j-th 1 in B, and select0(j) the index of the j-th 0. These queries are central to many succinct data structures, where one wants to support efficient navigation and counting on compressed representations.

Implementation typically uses a two-level index over the bit vector. Superblocks store the cumulative count of 1s up to their start, while smaller blocks within a superblock store local counts. This enables constant-time rank and select queries on static bit vectors, with extra space that is sublinear in n (often o(n) bits beyond the n bits of B). Classic approaches, such as the Jacobson construction and its refinements, illustrate the general technique of precomputing coarse and fine counts to achieve fast queries with small overhead.

Dynamic variants exist to handle insertions and deletions, but they are more complex and usually slower, often trading off time for space or relying on rebuilds and auxiliary structures. In practice, many libraries provide static rank/select data structures, and some offer dynamic versions with amortized guarantees.

Applications include compressed text indexing (for example, FM-indexes), wavelet trees, and other succinct data structures that require efficient counting and locating within large bit vectors. Implementations are available in libraries such as sdsl-lite, which expose rank and select support for binary sequences.