Rank-Select Indices Without Tears

Abstract

A rank-select index for a sequence $B=(b_1,\dots ,b_n)$ of $n$ bits is a data structure that, if provided with an operation to access $\Theta (\log n)$ arbitrary consecutive bits of $B$ in constant time (thus $B$ is stored outside of the data structure), can compute ${rank}_B(j)={\sum }_{i=1}^j{b}_i$ for given $j\in \{0,\dots ,n\}$ and ${select}_B(k)=\min \{j:{rank}_B(j)\ge k\}$ for given $k\in \{1,\dots ,{\sum }_{i=1}^n{b}_i\}$. We describe a new rank-select index that, like previous rank-select indices, occupies $O(n\log \log n/\log n)$ bits and executes $rank$ and $select$ queries in constant time. Its derivation is intended to be particularly easy to follow and largely free of tedious low-level detail, its operations are given by straight-line code, and we show that it can be constructed in $O(n/\log n)$ time.