Rank-Select Indices Without Tears

Tim Baumann, Torben Hagerup

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$…