$\sigma_{\ell}$.

Now we show how our approach can be used to obtain a fast and compact rank/select data structure. Suppose we have a data structure $T$ that supports [$\mathsf{access}$]{}, [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries on $t$; another structure ${\ensuremath{{M}}}$ that supports the same queries on ${\ensuremath{{m}}}$; and data structures $S_1, \ldots, S_{\left\lceil \lg^2 n
\right\rceil}$ that support the same queries on $s_1, \ldots, s_{\left\lceil
\lg^2 n \right\rceil}$. With these data structures we can implement $$\begin{aligned}
s.{\ensuremath{\mathsf{access}}}(i) & ~=~ & l.{\ensuremath{\mathsf{select}}}_\ell(s_\ell.{\ensuremath{\mathsf{access}}}(t.{\ensuremath{\mathsf{rank}}}_\ell(i))),
                        ~\textrm{where}~\ell = t.{\ensuremath{\mathsf{access}}}(i); \\[1ex]
s.{\ensuremath{\mathsf{rank}}}_a (i) & ~=~ & s_\ell.{\ensuremath{\mathsf{rank}}}_c (t.{\ensuremath{\mathsf{rank}}}_\ell (i)),
                        ~\textrm{where}~\ell = {\ensuremath{{m}}}.{\ensuremath{\mathsf{access}}}(a)
                        ~\textrm{and}~ c = {\ensuremath{{m}}}.{\ensuremath{\mathsf{rank}}}_\ell(a); \\[1ex]
s.{\ensuremath{\mathsf{select}}}_a (i) & ~=~ & t.{\ensuremath{\mathsf{select}}}_\ell (s_\ell.{\ensuremath{\mathsf{select}}}_c (i))
                        ~\textrm{where}~\ell = {\ensuremath{{m}}}.{\ensuremath{\mathsf{access}}}(a)
                        ~\textrm{and}~ c = {\ensuremath{{m}}}.{\ensuremath{\mathsf{rank}}}_\ell(a).\end{aligned}$$

We implement $T$ and ${\ensuremath{{M}}}$ as multiary wavelet trees [@FMMN07]; we implement each $S_\ell$ as either a multiary wavelet tree or an instance of Golynski et al.’s [@GMR06] [$\mathsf{access}$]{}/[$\mathsf{rank}$]{}/[$\mathsf{select}$]{} data structure, depending on whether $\sigma_\ell \leq \lg n$ or not. The wavelet tree for $T$ uses at most $n H_0 (t) + o (n)$ bits and operates in constant time, because its alphabet size is polylogarithmic. If $S_\ell$ is implemented as a wavelet tree, it uses at most $|s_\ell| H_0 (s_\ell) + o (|s_\ell|)$ bits and 