Zenn
⛳

LazySegTreeを書く

2025/02/13に公開
ポエム
idea

やること

AOJの遅延セグ木の問題を埋める。

RMQ (Range Min Query) and RUQ (Range Update Query)

https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_F

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>

using namespace std;
const int BASE = (1 << 19);
const int INF = (1LL << 31) - 1;  
using Int = long long;
template <typename T>
using Vec = vector<T>;

class LazySegTree {
    private:
        Vec<Int> tree, lazy;

    public:
        LazySegTree(int n) {
            tree.assign(2 * BASE, INF);
            lazy.assign(2 * BASE, -1);
        }

        void push(int pos, int sl, int sr) {
            if (lazy[pos] != -1) {
                tree[pos] = lazy[pos];
                if (sr - sl > 1) {
                    lazy[pos * 2] = lazy[pos];
                    lazy[pos * 2 + 1] = lazy[pos];
                }
                lazy[pos] = -1;
            }
        }

        void update(int ql, int qr, Int value, int sl = 0, int sr = BASE, int pos = 1) {
            push(pos, sl, sr);
            if (qr <= sl || sr <= ql) return;
            if (ql <= sl && sr <= qr) {
                lazy[pos] = value;
                push(pos, sl, sr);
                return;
            }
            int mid = (sl + sr) / 2;
            update(ql, qr, value, sl, mid, pos * 2);
            update(ql, qr, value, mid, sr, pos * 2 + 1);
            tree[pos] = min(tree[pos * 2], tree[pos * 2 + 1]);
        }

        Int get_min(int ql, int qr, int sl = 0, int sr = BASE, int pos = 1) {
            push(pos, sl, sr);
            if (qr <= sl || sr <= ql) return INF;
            if (ql <= sl && sr <= qr) return tree[pos];
            int mid = (sl + sr) / 2;
            return min(get_min(ql, qr, sl, mid, pos * 2), get_min(ql, qr, mid, sr, pos * 2 + 1));
        }
};

int main() {
    int n, q;
    cin >> n >> q;
    LazySegTree seg(n);
    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if (type == 0) {
            int s, t, x;
            cin >> s >> t >> x;
            seg.update(s, t + 1, x);
        } else {
            int s, t;
            cin >> s >> t;
            cout << seg.get_min(s, t + 1) << endl;
        }
    }
    return 0;
}

RSQ (Range Sum Query) and RAQ (Range Add Query)

https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_G

#include<iostream>
#include<vector>
using namespace std;

const int BASE = (1 << 19);
using Int = long long;
template <typename T>
using Vec = vector<T>;

class LazySegTree {
    private:
        Vec<Int> tree, lazy;

        void push(int pos, int sl, int sr) {
            if (lazy[pos] != 0) {
                tree[pos] += lazy[pos] * (sr - sl);
                if (sr - sl > 1) {
                    lazy[pos * 2] += lazy[pos];
                    lazy[pos * 2 + 1] += lazy[pos];
                }
                lazy[pos] = 0;
            }
        }

    public:
        LazySegTree(int n) {
            tree.assign(2 * BASE, 0);
            lazy.assign(2 * BASE, 0);
        }

        void update(int ql, int qr, Int value, int sl = 0, int sr = BASE, int pos = 1) {
            push(pos, sl, sr);
            if (qr <= sl || sr <= ql) return;
            if (ql <= sl && sr <= qr) {
                lazy[pos] += value;
                push(pos, sl, sr);
                return;
            }
            int mid = (sl + sr) / 2;
            update(ql, qr, value, sl, mid, pos * 2);
            update(ql, qr, value, mid, sr, pos * 2 + 1);
            tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
        }

        Int get_sum(int ql, int qr, int sl = 0, int sr = BASE, int pos = 1) {
            push(pos, sl, sr);
            if (qr <= sl || sr <= ql) return 0;
            if (ql <= sl && sr <= qr) return tree[pos];
            int mid = (sl + sr) / 2;
            return get_sum(ql, qr, sl, mid, pos * 2) + get_sum(ql, qr, mid, sr, pos * 2 + 1);
        }
};

int main() {
    int n, q;
    cin >> n >> q;
    LazySegTree seg(n);
    for(int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if (type == 0) { 
            int s, t, x;
            cin >> s >> t >> x;
            seg.update(s, t + 1, x); 
        } else {  
            int s, t;
            cin >> s >> t;
            cout << seg.get_sum(s, t + 1) << endl;
        }
    }
    return 0;
}

RMQ (Range Min Query) and RAQ (Range Add Query)

https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_H

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int BASE = (1 << 17);
const int INF = (1LL << 31) - 1;
using Int = long long;
template <typename T>
using Vec = vector<T>;

class LazySegTree {
    private:
        Vec<Int> tree, lazy;

        void push(int pos, int sl, int sr) {
            if (lazy[pos] != 0) {
                tree[pos] += lazy[pos];
                if (sr - sl > 1) {
                    lazy[pos * 2] += lazy[pos];
                    lazy[pos * 2 + 1] += lazy[pos];
                }
                lazy[pos] = 0;
            }
        }

    public:
        LazySegTree(int n) {
            tree.assign(2 * BASE, 0);
            lazy.assign(2 * BASE, 0);
        }

        void update(int ql, int qr, Int value, int sl = 0, int sr = BASE, int pos = 1) {
            push(pos, sl, sr);
            if (qr <= sl || sr <= ql) return;
            if (ql <= sl && sr <= qr) {
                lazy[pos] += value;
                push(pos, sl, sr);
                return;
            }
            int mid = (sl + sr) / 2;
            update(ql, qr, value, sl, mid, pos * 2);
            update(ql, qr, value, mid, sr, pos * 2 + 1);
            tree[pos] = min(tree[pos * 2], tree[pos * 2 + 1]);
        }

        Int get_min(int ql, int qr, int sl = 0, int sr = BASE, int pos = 1) {
            push(pos, sl, sr);
            if (qr <= sl || sr <= ql) return INF;
            if (ql <= sl && sr <= qr) return tree[pos];
            int mid = (sl + sr) / 2;
            return min(get_min(ql, qr, sl, mid, pos * 2),
                       get_min(ql, qr, mid, sr, pos * 2 + 1));
        }
};

int main() {
    int n, q;
    cin >> n >> q;
    LazySegTree seg(n);
    
    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if (type == 0) {  
            int s, t, x;
            cin >> s >> t >> x;
            seg.update(s, t + 1, x);
        } else {  
            int s, t;
            cin >> s >> t;
            cout << seg.get_min(s, t + 1) << endl;
        }
    }
    return 0;
}

RSQ (Range Sum Query) and RUQ (Range Update Query)

https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_I

#include<iostream>
#include<vector>
using namespace std;

const int BASE = (1 << 17);
using Int = long long;
template <typename T>
using Vec = vector<T>;

class LazySegTree {
    private:
        Vec<Int> tree, lazy;
        Vec<bool> pending;

        void push(int pos, int sl, int sr) {
            if (pending[pos]) {
                tree[pos] = lazy[pos] * (sr - sl);
                if (sr - sl > 1) {
                    lazy[pos * 2] = lazy[pos];
                    lazy[pos * 2 + 1] = lazy[pos];
                    pending[pos * 2] = pending[pos * 2 + 1] = true;
                }
                pending[pos] = false;
            }
        }

    public:
        LazySegTree(int n) {
            tree.assign(2 * BASE, 0);
            lazy.assign(2 * BASE, 0);
            pending.assign(2 * BASE, false);
        }

        void update(int ql, int qr, Int value, int sl = 0, int sr = BASE, int pos = 1) {
            push(pos, sl, sr);
            if (qr <= sl || sr <= ql) return;
            if (ql <= sl && sr <= qr) {
                lazy[pos] = value;
                pending[pos] = true;
                push(pos, sl, sr);
                return;
            }
            int mid = (sl + sr) / 2;
            update(ql, qr, value, sl, mid, pos * 2);
            update(ql, qr, value, mid, sr, pos * 2 + 1);
            tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
        }

        Int get_sum(int ql, int qr, int sl = 0, int sr = BASE, int pos = 1) {
            push(pos, sl, sr);
            if (qr <= sl || sr <= ql) return 0;
            if (ql <= sl && sr <= qr) return tree[pos];
            int mid = (sl + sr) / 2;
            return get_sum(ql, qr, sl, mid, pos * 2) + get_sum(ql, qr, mid, sr, pos * 2 + 1);
        }
};

int main() {
    int n, q;
    cin >> n >> q;
    LazySegTree seg(n);
    
    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if (type == 0) {  
            int s, t, x;
            cin >> s >> t >> x;
            seg.update(s, t + 1, x); 
        } else {  
            int s, t;
            cin >> s >> t;
            cout << seg.get_sum(s, t + 1) << endl;
        }
    }
    return 0;
}

まとめ

  • ミニマムの綴りが分からなかったんですけど、スルーしちゃいました。ごめんなさい。
  • SegTreeテンプレを某有名競プロYouTuberに倣って作ってから遅延評価ってどういうのだっけ？と考えながら書いていくとやりやすいなと思いました。Lazyの値はどういう値であるか、ということは常に自分に意識させておくとミスが減りそう。
  • 半開半閉区間にしています。
  • LazySegTreeの多様なパターンに思える問題らに対するコードをページ遷移なしで見比べれたらいいなと思っていたんだけど、見当たらなかったので作りました。
  • 至らない部分も散見されるかと思います。何かご意見や気付かれた点がありましたら、温かいご指摘いただけますと幸いです🙏

C++を速く書く方法模索中です、、

Discussion