Rustで競プロしててセグメント木・遅延伝搬セグメント木を使いたいことってありますよね。 大体ac-library-rsに実装されているものを使うと思うんですけれど、MonoidやMapMonoidというモノイドの実装をする必要があり、割と大変そうなので自分用にメモを残します。 (大嘘担当大臣していたらひっそりと教えてください)。
TL;DR
- たぶんこれを読むのが一番はやい(わかりやすい)と思います。 betrue12.hateblo.jp
セグメント木
Monoidトレイトを継承した構造体を実装します。
struct MyMonoid; impl Monoid for MyMonoid { type S = usize; // セグ木自体に乗せるオブジェクトの型 fn identity() -> Self::S { // 単位元 } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { // 演算操作 } } fn main() { let mut tree = Segtree::<MyMonoid>::from(vec![0; N]); // こんな感じに定義 }
usizeにおける加法の実装例
struct Add; impl Monoid for Add { type S = usize; fn identity() -> Self::S { 0_usize } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { a + b } } fn main() { let mut tree = Segtree::<Add>::from(vec![0; N]); }
ちなみに最大・最小・加法・乗法についてはビルトインで実装済みなので、それを利用するのが賢いと思います。
遅延伝搬セグメント木
概要
- 区間更新・区間クエリを効率的に捌ける便利なデータ構造
- 計算量
- 各ノードは以下の情報を持つ
- data: S
- lazy: F
- 子ノードの遅延している更新情報
- 以下の演算の定義が必要
- binary_operation: (S, S) -> S
- data同士の演算操作
- mapping: (F, S) -> S
- 親(あるいはクエリ)からの更新情報 F を自分のノードのdataに作用させる演算操作
- composition: (F, F) -> F
- 親(あるいはクエリ)からの更新情報 Fを子ノードに伝える必要がある場合に、lazy同士を合成する演算操作
- 複数回の更新操作を1度の更新操作にまとめるという意味
- (新しい操作, 過去の操作)になる。つまりという事ですね。
- 親(あるいはクエリ)からの更新情報 Fを子ノードに伝える必要がある場合に、lazy同士を合成する演算操作
- binary_operation: (S, S) -> S
- 区間更新
- 更新情報 F を受け取り、過不足なく区間を覆える要素にmapping操作でdataを更新する
- 子ノードが存在する場合、自身が持つlazyと更新情報Fをcomposition操作で更新する
利用方法
MapMonoidを継承したクラスを構造体を実装する。
struct MyMapMonoid; impl MapMonoid for MyMapMonoid { type M = MyMonoid; // 通常のセグメント木で使うモノイドの情報 data同士の操作やdata自体に関する定義 type F = usize; // 遅延更新情報の型 fn identity_map() -> Self::F { // 遅延更新情報の単位元 0_usize } fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S { // 親ノードor区間更新クエリから渡された更新情報(F)を自身が持つdata(S)に作用させる演算操作 ((F, S) => S) } fn composition(f: &Self::F, g: &Self::F) -> Self::F { // 親ノードor区間更新クエリから渡された更新情報(F1)を子ノードへ伝える更新情報(F2)とマージさせる演算操作 ((F, F) => F) } }
usizeにおける加法の実装例
struct MapMax; impl MapMonoid for MapMax { type M = Max<usize>; type F = usize; fn identity_map() -> Self::F { 0_usize } fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S { *f.max(x) } fn composition(f: &Self::F, g: &Self::F) -> Self::F { *f.max(g) } } fn main() { let mut lazyTree = LazySegtree::<MapMax>::from(vec![0; W]); }
lazyに区間長を持たせたい場合
mappingの引数に区間長が与えられていないため、区間更新で"範囲内の要素にする"みたいなことができなさそう。 しかしセグ木に乗せるデータ構造を以下のように工夫すればうまくいく。
#[derive(Clone)] // Cloneのサブクラスである必要がある struct MyData { value: usize, length: usize } fn main() { let mut lazyTree = LazySegtree::<MyMapMonoid>::from(vec![MyData { value: 0, length: 1 }; N]); // 利用するデータの範囲にlength=1を与えないとvalueが更新できない } struct MyMonoid; impl Monoid for MyMonoid { type S = MyData; fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { MyData { value: a.value + b.value, length: a.length + b.length } } fn identity() -> Self::S { MyData { value: 0, length: 0 } } } struct MyMapMonoid; impl MapMonoid for MyMapMonoid { type M = MyMonoid; type F = usize; fn identity_map() -> Self::F { 0_usize } fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S { MyData { value: x.value + f * x.length, length: x.length } } fn composition(f: &Self::F, g: &Self::F) -> Self::F { f + g } }