競プロ用ライブラリを作る Advent Calendar 2024の24日目です.
MasterTreeって?
皆さんは遅延伝搬反転可能乱択平衡二分木を知っていますか?
これと同じノリで思いつく機能を片っ端から盛り込んだ最強データ構造を作ります.
列に対して以下のことを全部$O(\log N)$でします.
- 複製する
- 指定された位置に指定した値を挿入する
- 指定された位置の値を削除する
- 2つの列をくっつける
- 列を指定した位置で2つに分割する
- 指定された区間のモノイドの総積を求める
- モノイドに遅延伝搬可能な写像を指定した区間に作用させる
- 列を前後反転させる
仕組み
LazySegmentTree + BinaryTree + Persistent SegmentTree + 他色々の知識を全部合体させます.
BinaryTreeではWeight Balanced Treeというもので平衡させましたが, 操作の種類が多くて証明が大変なので, ここではRBSTという別の方法を使います. (元ネタの遅延伝(略)木と同じ方法です)
「全部の頂点が当確率で根になる」というもので, 例えば要素数$N$の木と要素数$M$の木をマージすると, $N/(M+N)$の確率で要素数$N$の木の根だった要素が, $M/(M+N)$の確率で要素数$M$の木の根だった要素が新しい木の根になるようにします.
とてもふわっとしたサンプルコード
fn merge(left: Tree, right: Tree) -> Tree {
if rand() < left.size() / (left.size() + right.size()) {
// 左側の木の根を新しい木の根に採用 (左の木の右の部分木でマージを行う)
left.subtree.right = merge(left.subtree.right, right);
return left;
} else {
// 右側の木の根を新しい木の根に採用 (右の木の左の部分木でマージを行う)
right.subtree.left = merge(left, right.subtree.left);
return right;
}
}
実質平衡条件が存在してないようなもので, 考えることが減るので機能を増やしやすいです.
実装
やってしまいましたね. 800行くらいあります.
まとめ
いかがでしたか?
明日はライブラリの混沌を治めます.