Maintaining the cycle structure of dynamic permutations
Zsuzsanna Lipták, Francesco Masillo, Gonzalo Navarro · arXiv (Cornell University) · 2023
We present a new data structure for maintaining dynamic permutations, which we call a $\textit{forest of splay trees (FST)}$. The FST allows one to efficiently maintain the cycle structure of a permutation $π$ when the allowed updates are transpositions. The structure stores one conceptual splay tree for each cycle of $π$, using the position within the cycle as the key. Updating $π$ to $τ\cdotπ$, for a transposition $τ$, takes $\mathcal{O}(\log n)$ amortized time, where $n$ is the size of $π$. The FST computes any $π(i)$, $π^{-1}(i)$, $π^k(i)$ and $π^{-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.