Rustでセグメント木に乗せる際のメモ

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]);
}

atcoder.jp

ちなみに最大・最小・加法・乗法についてはビルトインで実装済みなので、それを利用するのが賢いと思います。

遅延伝搬セグメント木

概要

区間更新・区間クエリを効率的に捌ける便利なデータ構造
計算量
- 構築: $O(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$ , 過去の操作 $g$ )になる。つまり $f\circ g(x) =f(g(x))$ という事ですね。
区間更新
1. 更新情報 F を受け取り、過不足なく区間を覆える要素にmapping操作でdataを更新する
2. 子ノードが存在する場合、自身が持つ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]);
}

atcoder.jp

lazyに区間長を持たせたい場合

mappingの引数に区間長が与えられていないため、区間更新で"範囲内の要素に $+a$ する"みたいなことができなさそう。しかしセグ木に乗せるデータ構造を以下のように工夫すればうまくいく。

#[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
    }
}

cf. AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA

たれながし

色々雑多に書きます