$[1..\sigma]$ (using [$\mathsf{select}$]{}), find an element’s rank among the elements with the same image, or the size of the preimage (using [$\mathsf{rank}$]{}), etc.

Let $f: [1..n] \rightarrow [1..\sigma]$ be a surjective function. We can represent $f$ using $nH_0(f) + o(n)(H_0(f)+1)$ bits so that any $f(i)$ can be computed in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time. Moreover, each element of $f^{-1}(a)$ can be computed in ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma} \right)}}$ time, and $|f^{-1}(a)|$ requires time ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma\lg\lg\lg\sigma} \right)}}$. Alternatively we can compute $f(i)$ and $|f^{-1}(a)|$ in time ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma} \right)}}$ and deliver any element of $f^{-1}(a)$ in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time.

We can also achieve interesting results with our theorems from Section \[sec:permutations\], as runs arise naturally in many real-life functions. For example, suppose we decompose $f
(1), \ldots, f(n)$ into $\rho$ interleaved non-increasing or non-decreasing runs. Then we can store it as a combination of the permutation $\pi$ that stably sorts the values $f(i)$, plus a compressed [$\mathsf{rank}$]{}/[$\mathsf{select}$]{} data structure storing a binary string $b[1..n+\sigma+1]$ with $\sigma+1$ bits set to 1: if $f$ maps $i$ values in $[1..n]$ to a value $j$ in $[1..\sigma]$ then, in $b$, there are $i$ bits set to 0 between the $j$th and $(j + 1)$th bits set to 