Maintaining the cycle structure of dynamic permutations

We present a new data structure for maintaining dynamic permutations, which we call a $\mathit{\text{forest}}\mathit{\text{of}}\mathit{\text{splay}}\mathit{\text{trees}}\mathit{\text{(FST)}}$. The FST allows one to efficiently maintain the cycle structure of a permutation $\pi$ when the allowed updates are transpositions. The structure stores one conceptual splay tree for each cycle of $\pi$, using the position within the cycle as the key. Updating $\pi$ to $\tau \cdot \pi$, for a transposition $\tau$, takes $\mathcal{O}(\log n)$ amortized time, where $n$ is the size of $\pi$. The FST computes any $\pi (i)$, ${\pi }^{-1}(i)$, ${\pi }^k(i)$ and ${\pi }^{-k}(i)$, in $\mathcal{O}(\log n)$ amortized time. Further, it supports cycle-specific queries such as determining whether two elements belong to the same cycle, flip a segment of a cycle, and others, again within $\mathcal{O}(\log n)$ amortized time.