遅延セグ木の王、遅延セグキングのチートシート

　アルメリアさんが、遅延セグ木（遅延セグメントツリー）について、とても便利な チートシート を公開してくださっています。

　しかし、慣れていない人にとっては、いつ何を使えばいいかがわかりづらいです。

　そこで、本記事では、持てる情報をなるべく持った遅延セグ木の王、遅延セグキングのチートシートを紹介したいと思います。

　これがその最強のチートシートだ！

const long long INF = 8e18;
struct S{
    long long sum;     // 区間の合計値
    long long min_val; // 区間の最小値
    long long max_val; // 区間の最大値
    int size;          // 区間のサイズ
};
using F = long long;
const F ID = INF;
S op(S a, S b){
    return S{
        a.sum + b.sum,
        std::min(a.min_val, b.min_val),
        std::max(a.max_val, b.max_val),
        a.size + b.size
    };
}
S e(){
    return S{
        0,
        INF,
        -INF,
        0,
    };
}
S mapping(F f, S x){
    if(f != ID){
        x.sum = f * x.size;
        x.min_val = f;
        x.max_val = f;
    }
    return x;
}
F composition(F f, F g){
    return (f == ID ? g : f);
}
F id(){
    return ID;
}
long long target;
bool f_sum(S prod){
    return prod.sum <= target;
}
bool f_increase(S prod){
    return prod.max_val <= target;
}
bool f_decrease(S prod){
    return prod.min_val >= target;
}
bool f_same(S prod){
    return prod.max_val <= target && prod.min_val >= target;
}

嬉しいところ

1. 何をコピペすればいいか迷わなくてよい
2. 複数の用途にひとつのデータ構造で対応できる
3. 同一値連続区間が求められる

　「1.」については特に説明はいらないと思うので、「2.」と「3.」について、使用例を添えて説明していきます。

複数の用途にひとつのデータ構造で対応できる

　二分探索は最大値を基準に行いたいけど、クエリの結果は区間和が欲しい、みたいな時でも、どちらの情報も持っているので対応できます。

使用例

int main(){
    int n;
    cin >> n;
    vector<int> h(n);
    cin >> h;
    lazy_segtree<S,op,e,F,mapping,composition,id> seg(n);
    rep(i,n){
        seg.set(i,{0,INF,-INF,1});
    }
    vector<ll> ans;
    rep(i,n){
        target = h[i];
        int idx = seg.min_left<f_increase>(i+1);
        seg.apply(idx,i+1,target);
        ans.push_back(seg.all_prod().sum+1);
    }
    cout << ans << endl;
}

同一値連続区間が求められる

　「最小値が $x$ 以上であるような区間」と「最大値が $x$ 以下であるような区間」の共通部分を取ると、「値が $x$ であるような区間」となります。最小値と最大値をふたつ持つことによって、この探索が可能になります。

使用例

int main(){
    int n,q;
    cin >> n >> q;
    lazy_segtree<S,op,e,F,mapping,composition,id> seg(n);
    rep(i,n){
        seg.set(i,{i+1,i+1,i+1,1});
    }
    vector<int> ans(n+1,1);
    while(q--){
        int t;
        cin >> t;
        if(t == 1){
            int x,c;
            cin >> x >> c;
            x--;
            target = seg.get(x).sum;
            int left = seg.min_left<f_same>(x);
            int right = seg.max_right<f_same>(x);
            ans[target] -= right-left;
            ans[c] += right-left;
            seg.apply(left,right,c);
        }
        if(t == 2){
            int c;
            cin >> c;
            cout << ans[c] << endl;
        }
    }
}

嬉しくないところ

区間加算ができない

　上のチートシートは区間変更限定です。区間加算を扱うためには、新たな遅延セグキングを生み出してください。

区間最小値（最大値）更新ができない

　これは遅延セグ木では不可能で、Beats という更にハイレベルなデータ構造が必要なようです。