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
Dynamic variants exist to handle insertions and deletions, but they are more complex and usually slower, often
Applications include compressed text indexing (for example, FM-indexes), wavelet trees, and other succinct data structures that