Rust で ACL の LazySegtree を使う。

# Rust で ACL の LazySegtree を使う

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

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

- [AtCoder LibraryのLazy Segtreeの使い方](https://betrue12.hateblo.jp/entry/2020/09/22/194541)

## 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` を実装してみます。

```rust
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` を簡単に定義できます。

```rust
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` を実装します。

```rust
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` を設計するとよいでしょう。