部分永続 Union Find Θ(log(log(n)))

概要

部分永続 Union Find のアルゴリズムの変種を考えました
注意: 実測では使い物にならない気がします

空間計算量 $\mathrm{O}(q + n\log(\log(n)))$

- $\mathtt{init}(n)$
単一の要素からなる集合 $n$ 個で初期化する
時間計算量 $\Theta(n)$

- $\mathtt{unite}(x, y)$
$x$ と $y$ が属する集合を併合する
時間計算量 $\Theta(\log(\log(n))) \ \mathrm{expected} \ \mathrm{amortized}$

- $\mathtt{find}(t, x)$
$t$ 回目に $\mathtt{unite}$ が呼ばれた直後に $x$ が属していた集合の代表元を取得する
時間計算量 $\Theta(\log(\log(n)))$

- $\mathtt{size}(t, x)$
$t$ 回目に $\mathtt{unite}$ が呼ばれた直後に $x$ が属していた集合の要素数を取得する
時間計算量 $\Theta(\log(\log(n))) \ \mathrm{expected}$

アルゴリズム

通常の Union Find のアルゴリズムにおいて、weighted union rule は適用し、経路圧縮は行わないことで得られる木を考えます。 $\mathtt{find}(t, x)$ は、この木において $x$ の祖先で時刻 $t$ にまだ根だったものの中で最も深いものを発見すると表現できます。もし $\mathtt{unite}$ が全て事前に与えられているならば、ダブリングを用いることで $\Theta(\log(\log(n)))$ の時間計算量で $\mathtt{find}$ に答えることが出来ます。 weighted union rule により木の高さが $\Theta(\log(n))$ に抑えられることに注意してください。

よって、 $\mathtt{size}$ を一旦忘れると、ダブリングのための情報（各頂点について、 $2^i$ 個上の頂点）を $\mathtt{unite}$ の度に更新できれば良いです。 $y$ を $x$ の子にするとき、新たに情報を更新する必要があるのは $y$ の子孫で $x$ からの距離が二冪の頂点です。各頂点 $v$ が $\mathtt{list}(v, i)$ : $v$ の子孫で $v$ からの距離が $2^i$ の頂点のリストを管理していれば、これは効率的に列挙可能です。例えば、 $x$ から距離 $8$ の頂点は $x$ から距離 $4$ の頂点から更に距離 $4$ の頂点です。ポテンシャルとして「 $\min \lbrace n, q \rbrace\log(\log(\min \lbrace n,q \rbrace)) -$ 計算されたダブリングのテーブルの要素数」を考えれば、テーブルの更新の時間計算量はならすことができます。

$\mathtt{size}$ を処理するために、各頂点 $v$ は $(t, s)$ : 時刻 $t$ に $v$ を代表元とする集合の要素数が $s$ に更新された、という情報を管理します。 $\mathtt{size}(t, x)$ クエリは $\mathtt{find}(t, x)$ において要素数が $t$ の直前に更新されたときの対応するデータを報告すればよいです。 $t$ は $q$ を超えないため、これは Y-fast-trie を用いて $\Theta(\log(\log(q))) \ \mathrm{expected}$ で処理できます。長さ $q$ のテーブルを持って適宜変換することにより、 $\mathtt{unite}$ が呼ばれた回数ではなく $\mathtt{unite}$ で実際に集合が併合された回数を時刻として利用できます。これにより時刻は常に $n$ 未満になり、時間計算量は $\Theta(\log(\log(n))) \ \mathrm{expected}$ になります。