exponentiation ($\pi^k(i)$, $\pi^{-k}(i)$) within compressed space. Munro [[*et al.*]{}]{} [@MRRR03] reduced the problem of supporting exponentiation on a permutation $\pi$ to the support of the direct and inverse application of another permutation, related but with quite distinct runs than $\pi$. Combining any of our results (Theorem \[thm:runs\] to \[thm:contiguous strict runs\]) with this technique does yield a compression, but without any relation to the runs of $\pi$. The following construction, extending the technique from Munro [[*et al.*]{}]{} [@MRRR03], retains the compressibility properties of $\pi$ by building a companion data structure that uses small space to support the exponentiation, thus allowing the compression of the main data structure with any of Theorems \[thm:runs\] to \[thm:contiguous strict runs\].

\[thm:exponent\] Suppose we have a data structure $D$ that stores a permutation $\pi$ on $n$ elements and supports queries $\pi()$ in time $g (\pi)$. Then for any $t \leq n$, we can build a succinct index that takes ${\ensuremath{\mathcal{O}\left( {(n / t) \lg n} \right)}}$ bits and, when used in conjunction with $D$, supports $\pi^k()$ and $\pi^{-k}()$ queries in ${\ensuremath{\mathcal{O}\left( {t\,g (\pi)} \right)}}$ time.

We decompose $\pi$ into its cycles and, for every cycle of length at least $t$, store the cycle’s length and 