Optimal-Time Move Structure Construction

Nathaniel K. Brown, Ahsan Sanaullah, Shaojie Zhang +1

The move structure represents a permutation $\pi$ of $[0,n)$ by partitioning the domain into $O(r)$ disjoint, contiguously permuted intervals, with $r$ being the minimum number of su…