競プロ用ライブラリを作る Advent Calendar 2024の17日目です.
Persistent UnionFindって?
過去の情報を取得できるUnionFindです.
仕組み
1つ目の方法として, 永続配列の上でUnionFindを実装する, という方法があります. これで各種クエリがならし$O(\log N\alpha(N))$です.
ここでは違う方法で実装します.
一旦「経路圧縮していないUnionFindの操作」を見てみましょう.
まずはこちら, 何もしていないUnionFindです.
AとBの集合をマージしましょう. マージした順に矢印に番号を書きます.
DとEもマージします.
AとC, AとDをマージします.
このように, 各操作では「マージに対応する辺の追加」以外の操作は行われていないことが分かります.
最後の状態の時, 番号が3以上の辺を無視してみると (図では点線にしてみます)
見比べると, DとEをマージした段階までの状態と一致します. ということで, こういう風に辺に操作の番号を付けて, 適切に無視することで過去の情報を見ることが出来ます.
実装
上記をそのまま実装します. UnionFindを実装したことがあれば楽々ですね.
まとめ
いかがでしたか?
明日も永続データ構造シリーズをします.