セグ木を改造するとたのしいという話

　またもセグ木の話。

　セグ木にはふたつの弱点があります。……ということにさせてください。

• add がない
• 応用範囲がせまい

　このふたつを解決するためにセグ木を改造すると楽しいという話をします。

add がない

　実装にもよりますが、セグ木のライブラリ（ここでは ACL を基準とします）には、set があっても add がないです。なので、例えば $1$ を加算をする際には、

• seg.set(i,set.get(i)+1)

　みたいな処理をしなければならず、微妙にめんどくさいです。

　なお、代表として add としましたが、xor でも max でも min でも同様の問題があります。

　要は、何らかのモノイド演算を apply として、

• seg.apply(i,1)

　みたいに書きたい。まあ、ライブラリをいじるなり、自作関数を用意するなりいくらでも方法はあるのですが、なるべく最小限の手間で対応したい。そこで、ACL そのままでも対応可能な技を見つけました。

　それは、遅延セグ木 を使うということです。遅延セグ木の apply は本来、区間作用用の命令ですが、これを[i,i+1) の範囲に作用させれば、一点作用と同じことをしていることになります。

　遅延セグ木の設定には、

• mapping
• composition
• id

　の設定が必要になり、それらの説明はけっこうめんどくさいのですが、一点作用なら適当に書いても大丈夫 です。より正確に言うと、本来であれば、これらの計算には「区間作用させたときにどうなるか」を考えることが必要なのですが、一点作用を前提とするならばそれを考えなくてよくなります（当然ながら、区間作用させたらバグる場合がほとんどです）。

　論より証拠、ということで、これが add 対応セグ木になります。

#include <atcoder/lazysegtree>
#include <iostream>
#include <vector>
using namespace std;
using namespace atcoder;
using ll = long long;

ll op(ll a, ll b) {
    return a + b;
}

ll e() {
    return 0;
}

ll mapping(ll f, ll x) {
    return f + x;
}

ll composition(ll f, ll g) {
    return f + g;
}

ll id() {
    return 0;
}

int main() {
    int n = 5;
    vector<ll> init(n, 1);
    lazy_segtree<ll, op, e, ll, mapping, composition, id> seg(init);

    for (int i = 0; i < n; i++) {
        cout << seg.get(i) << " ";
    }
    cout << endl;

    seg.apply(0, 1, 1);
    seg.apply(2, 3, 1);

    for (int i = 0; i < n; i++) {
        cout << seg.get(i) << " ";
    } // 2 1 2 1 1
    cout << endl;

    cout << seg.all_prod() << endl; // 7 総和もOK

    seg.apply(0, 4, 1); // これはバグる

    for (int i = 0; i < n; i++) {
        cout << seg.get(i) << " ";
    } // 3 2 3 2 1
    cout << endl; // 一見大丈夫に見えるが

    cout << seg.all_prod() << endl; // 8 総和がおかしい
}

　$1$ を超える幅で apply するとバグります。本来は、区間和は区間サイズを持つ必要があるにも関わらず、その設定をサボっているためです。しかし、一点作用だけならバグりません。

　min ではこうなります。

#include<atcoder/lazysegtree>
using namespace atcoder;
ll op(ll a,ll b){
    return min(a,b);
}
ll e(){
    return 1e18;
}
ll mapping(ll f,ll x){
    return min(f,x);
}
ll composition(ll f,ll g){
    return min(f,g);
}
ll id(){
    return 1e18;
}

　ほとんどの場合、op でやりたい操作と apply でやりたい操作は同じモノイド演算だと思うので、mapping にも composition にも同じ演算をコピーしてやれば大丈夫なはずです。

応用範囲をひろげる

　セグ木の本質を表すと、平衡二分木にすることによって計算量を押さえているということになります。

　上から順に、足し算なり最小値なりをまとめていくと、どんどん大きい区間での代表値がまとまっていきます。

応用例：選挙速報

　少し変わった応用方法を紹介します。

要約：候補者がどんどん投票されていく。各段階で、最も投票数が多い（同数の場合は、番号が若い）人はだれか？

　想定解としてはうまい逐次更新の方法がありますが、実はセグ木に載せて通すこともできます。

　上のような関係が成り立つためです。末端の選挙区では $1$ 名しか立候補者がいないので、自動的にその人が代表になります（$0$ 票だったとしても、$0$ 票でトップ当選です）。選挙区をマージするときは、投票数が多い方、そうでないならば、番号が若い方を勝者とすれば大丈夫です。

　こうすれば、各一点更新に対して、全体の反映にかかる時間はたかだか $O(\log{N})$ で済ませることが可能です。

#include <iostream>
#include <atcoder/lazysegtree>
using namespace std;
using namespace atcoder;

// セグメント木のノードが持つ構造体
struct S {
    int value; // 値（加算された回数）
    int idx;   // インデックス（位置）
};

// 2つのノードをマージする関数
S op(S a, S b) {
    if (a.value != b.value) {
        return (a.value > b.value) ? a : b;
    } else {
        return (a.idx < b.idx) ? a : b;
    }
}

// 単位元（初期値）
S e() {
    return {0, 0};
}

// 遅延評価で適用される関数（整数fをSに適用）
S mapping(int f, S x) {
    x.value += f;
    return x;
}

// 遅延の合成（後の操作が前の操作に追加される）
int composition(int f, int g) {
    return f + g;
}

// 遅延の単位元
int id() {
    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;

    // 長さ n+1 の lazy_segtree を定義（各位置に {0, index} を設定）
    lazy_segtree<S, op, e, int, mapping, composition, id> seg(n + 1);
    for (int i = 0; i <= n; ++i) {
        seg.set(i, {0, i});
    }

    // クエリ処理
    for (int i = 0; i < m; ++i) {
        int a;
        cin >> a;
        // 位置 a に +1 を加算（a番目だけ）
        seg.apply(a, a + 1, 1);

        // 現在の最大値を持つインデックスを出力
        cout << seg.all_prod().idx << endl;
    }

    return 0;
}

　遅延セグ木の設定さえ済ませれば、事実上の更新と答えの出力が、

        seg.apply(a, a + 1, 1);
        cout << seg.all_prod().idx << endl;

　この $2$ 行で可能になります。

　こうして見ると、セグ木の op の本質は マージして都合の良い情報を残す ということであることがわかります。

　セグ木の計算を成り立たせるためには、

• 計算の結果が順序に拠らない（どのような順番でマージしてもいい）
• 計算の結果に影響を与えない数が存在する（平衡二分木を形成するため）

　という性質が必要ですが、これがいわゆる モノイド の性質になります。

応用例：mex

　わざわざ改造するまでもないですが（max_right で同じことができるため）、シンプルな改造例として mex（未使用の中で最小の数）を求めてみます。

　こんな感じのマージ構造を定義すればよいです。付属情報として size が必要なので、構造体で定義します。

#include<atcoder/lazysegtree>
using namespace atcoder;
struct S
{
    /* data */
    int value;
    int size;
};
S op(S a,S b){
    if(a.value>=a.size){
        return {a.size+b.value,a.size+b.size};
    }else{
        return {a.value,a.size+b.size};
    }
}
S e(){
    return {0,1};
}
S mapping(int f,S x){
    x.value += f;
    return x;
}
int composition(int f,int g){
    return f+g;
}
int id(){
    return 0;
}

一般論

　バケット的な解法を使うとき、各区間から都合の良い情報だけをうまく抜き出してマージできるとき、セグ木で処理できます。