1s and $p$ 0s. Calculations similar to those above show we can store $P$ in $o (n) \lg \sigma$ bits and support [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time [@RRR02]. With $P$ we can compute, in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time, the total number of $a$’s across the first $r$ blocks containing $a$’s, and the smallest $r$ such that the first $r$ blocks containing $a$’s contain at least $j$ of them.

To perform $s.{\ensuremath{\mathsf{rank}}}_a (j)$, we compute the index $j' = \lceil j / b \rceil$ in $s'$ of the block containing the $j$th character of $s$; use Ferragina and Venturini’s data structure and $B$ to find number of $a$’s within $s' [j']$ up to position $j \bmod b$; use $R$ to find the number of blocks in $s' [1.. j' - 1]$ that contain $a$’s; and use $P$ to find the total number of $a$’s in those preceding blocks. To perform $s.{\ensuremath{\mathsf{select}}}_a (j)$, we use $P$ to find the smallest $r$ such that the first $r$ blocks containing $a$’s contain at least $j$ of them; use $P$ again to find the total number $t$ of $a$’s in the first $r - 1$ blocks containing $a$’s; use $R$ to 