Rust で ACL の LazySegtree を使う

AtCoder Library (ACL) に含まれる LazySegtree は、遅延伝播セグメントツリー (Lazy Segment Tree) を簡単に利用できる便利なデータ構造です。本記事では、Rust で ACL の LazySegtree を使う方法を解説します。

前提知識

LazySegtree を理解するために、以下の記事を読むことを推奨します。

• AtCoder LibraryのLazy Segtreeの使い方

LazySegtree の基本構造

ACL の LazySegtree は、

• 作用モノイド (MapMonoid)
• データモノイド (Monoid)

の 2 つを定義する必要があります。

LazySegtree の型パラメータと、ACL C++ 版の引数との対応は以下の通りです。

C++ 版引数	Rust 版 LazySegtree の対応
S	MapMonoid::M::S の定義
op	MapMonoid::M::binary_operation の定義
e	MapMonoid::M::identity の定義
F	MapMonoid::F の定義
mapping	MapMonoid::mapping の定義
composition	MapMonoid::composition の定義
id	MapMonoid::identity_map の定義

LazySegtree を利用するためには、MapMonoid を満たす型を実装し、その中に Monoid を満たす型を含める必要があります。

<区間最小値, 区間加算> の LazySegtree の実装

まず、最も基本的な例として、区間最小値 (RMQ) に対する区間加算を行う LazySegtree を実装してみます。

use std::i64;
use ac_library::{LazySegtree, MapMonoid, Monoid};

struct U;

impl Monoid for U {
    type S = i64;
    fn identity() -> Self::S {
        i64::MAX
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        *a.min(b)
    }
}

struct T;

impl MapMonoid for T {
    type M = U;
    type F = i64;
    fn identity_map() -> Self::F {
        0
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        *f + *x
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        *f + *g
    }
}

fn main() {
    let mut ls = LazySegtree::<T>::new(10);
}

この実装では、

• U で区間最小値のモノイドを定義 (i64::MAX を単位元として min を二項演算に採用)
• T で MapMonoid を定義し、作用素として区間加算を実装

という形になっています。

ac_library の Min<T> を使った簡略化

ACL には Min<T> という便利な型が用意されており、上記の Monoid を簡単に定義できます。

use ac_library::{LazySegtree, MapMonoid, Min, Monoid};

struct T;

impl MapMonoid for T {
    type M = Min<i64>;
    type F = i64;
    fn identity_map() -> Self::F {
        0
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        *f + *x
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        *f + *g
    }
}

この Min<i64> を用いると、Monoid の定義が不要になり、より簡潔な実装が可能になります。ただし、Min<T> や Max<T> は Rust の組み込み整数型 (i64, i32 など) にしか対応していない(何らかのトレイトを満たせば使えるというわけではない。)ため、他の型 (多倍長整数など) を使いたい場合は前述の手動実装が必要になります。
Min<i64>の定義されているファイルにただのセグメントツリー用の Additive<T>(, Multiplicative<T>) が定義されていますが、そもそも<区間和, 区間更新>, <区間和, 区間加算> いずれも遅延伝播セグメントツリーでは要素数の情報の保持が必須なので使えません。

注意点として、ls.set(p, x) を繰り返してすべての要素を初期化してから他の機能を利用しないと、内部でf(>0) + i64::MAXが原因のオーバーフローを起こします。

<区間和, 区間更新> の LazySegtree の実装

次に、区間和 (RSQ) に対する区間更新を行う LazySegtree を実装します。

struct U;

impl Monoid for U {
    type S = (i64, i64); // (合計値, 要素数)
    fn identity() -> Self::S {
        (0, 1)
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        (a.0 + b.0, a.1 + b.1)
    }
}

struct T;

impl MapMonoid for T {
    type M = U;
    type F = Option<i64>;
    fn identity_map() -> Self::F {
        None
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        match *f {
            Some(v) => (v * x.1, x.1),
            None => *x,
        }
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        match *f {
            Some(_) => *f,
            None => *g,
        }
    }
}

この実装では、

• U で区間和のモノイドを定義し、値と要素数をタプルで保持
• T で MapMonoid を定義し、作用素として区間更新 (Some(v) の場合は v * 要素数 を設定)

という形になっています。

まとめ

ACL の LazySegtree は、区間操作を効率的に処理できる強力なデータ構造です。Rust では ac_library を利用することで、C++ の LazySegtree に相当する機能を簡単に実装できます。

• Monoid を定義し、identity と binary_operation を実装
• MapMonoid を定義し、mapping と composition を実装
• ac_library の Min<T> や Max<T> を使うと簡略化可能

実際の競技プログラミングで活用する際は、用途に応じて適切な Monoid と MapMonoid を設計するとよいでしょう。