Maintaining the cycle structure of dynamic permutations

Abstract

We present a new data structure for maintaining dynamic permutations, which we call a $\text{forest of splay trees (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.