느리게 갱신되는 구간합 세그먼트 트리 비재귀 템플릿(SegmentTree With Lazy Propagation Template)

< 최종 수정 일: 2024-12-31 > : destructor 추가

template<typename T>
class LazySegmentTree {
    private:
        const int n;
        T *tree, *lazy, *len;

        void init(vector<T> &a) {
            for(int i = 0; i < n; i++) {
                len[n + i] = 1;
                tree[n + i] = a[i];
            }
            for(int i = n - 1; i > 0; i--) {
                len[i] = len[i << 1] << 1;
                tree[i] = tree[i << 1] + tree[i << 1 | 1];
            }
        }

        void apply(int p, T val) {
            tree[p] += val * len[p];
            if(p < n) lazy[p] += val;
        }

        void build(int p) {
            for(p >>= 1; p > 0; p >>= 1) {
                tree[p] = tree[p << 1] + tree[p << 1 | 1] + lazy[p] * len[p];
            }
        }

        void push(int p) {
            for(int h = __lg(p); h > 0; h--) {
                int cur = p >> h;
                if(lazy[cur] != 0) {
                    apply(cur << 1, lazy[cur]);
                    apply(cur << 1 | 1, lazy[cur]);
                    lazy[cur] = 0;
                }
            }
        }

    public:
        LazySegmentTree(vector<T> &a) : n(a.size()) {
            tree = new T[n << 1]();
            lazy = new T[n << 1]();
            len = new T[n << 1]();
            init(a);
        }

        ~LazySegmentTree() {
            delete [] tree;
            delete [] lazy;
            delete [] len;
        }

        void update_point(int p, T val) {
            for(tree[p += n] = val; p > 1; p >>= 1) {
                tree[p >> 1] = tree[p] + tree[p ^ 1];
            }
        }

        void update_range(int l, int r, T val) {
            for(int L = l + n, R = r + n; L < R; L >>= 1, R >>= 1) {
                if(L & 1) apply(L++, val);
                if(R & 1) apply(--R, val);
            }
            build(l + n);
            build(r + n - 1);
        }

        T query(int l, int r) {
            T ret{};
            push(l += n);
            push((r += n) - 1);
            for(; l < r; l >>= 1, r >>= 1) {
                if(l & 1) ret += tree[l++];
                if(r & 1) ret += tree[--r];
            }
            return ret;
        }
};

 

느리게 갱신되는 세그먼트 트리 템플릿입니다. 비재귀로 구현했습니다. 레퍼런스가 많이 없어서 구현하는데 좀 시간이 걸렸었습니다. 원리에 대한 건 다른 곳에서 찾아보십쇼,, 써볼려고 했는데 저보다 더 잘 설명하신 분들이 많아요 이것도 구간합으로 구현되어있기 때문에 다른 연산에 대해선 수정이 필요합니다. 같은 유형 문제를 풀면서 XOR과 OR연산에 대해서도 수정해서 썼었는데 기회가 되면 올려보겠습니다.

 

스니펫에 추가해서 쓰시면 됩니당.

 

< 사용 예시 >

1. 백준 10999번 구간 합 구하기 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

template<typename T>
class LazySegmentTree {
    private:
        const int n;
        T *tree, *lazy, *len;

        void init(vector<T> &a) {
            for(int i = 0; i < n; i++) {
                len[n + i] = 1;
                tree[n + i] = a[i];
            }
            for(int i = n - 1; i > 0; i--) {
                len[i] = len[i << 1] << 1;
                tree[i] = tree[i << 1] + tree[i << 1 | 1];
            }
        }

        void apply(int p, T val) {
            tree[p] += val * len[p];
            if(p < n) lazy[p] += val;
        }

        void build(int p) {
            for(p >>= 1; p > 0; p >>= 1) {
                tree[p] = tree[p << 1] + tree[p << 1 | 1] + lazy[p] * len[p];
            }
        }

        void push(int p) {
            for(int h = __lg(p); h > 0; h--) {
                int cur = p >> h;
                if(lazy[cur] != 0) {
                    apply(cur << 1, lazy[cur]);
                    apply(cur << 1 | 1, lazy[cur]);
                    lazy[cur] = 0;
                }
            }
        }

    public:
        LazySegmentTree(vector<T> &a) : n(a.size()) {
            tree = new T[n << 1]();
            lazy = new T[n << 1]();
            len = new T[n << 1]();
            init(a);
        }

        ~LazySegmentTree() {
            delete [] tree;
            delete [] lazy;
            delete [] len;
        }

        void update_point(int p, T val) {
            for(tree[p += n] = val; p > 1; p >>= 1) {
                tree[p >> 1] = tree[p] + tree[p ^ 1];
            }
        }

        void update_range(int l, int r, T val) {
            for(int L = l + n, R = r + n; L < R; L >>= 1, R >>= 1) {
                if(L & 1) apply(L++, val);
                if(R & 1) apply(--R, val);
            }
            build(l + n);
            build(r + n - 1);
        }

        T query(int l, int r) {
            T ret{};
            push(l += n);
            push((r += n) - 1);
            for(; l < r; l >>= 1, r >>= 1) {
                if(l & 1) ret += tree[l++];
                if(r & 1) ret += tree[--r];
            }
            return ret;
        }
};

int n, m, k;

int main() {
    fastio(nullptr, false);

    cin >> n >> m >> k;

    vl a(n);
    for(auto &x : a) cin >> x;

    LazySegmentTree<ll> lazySegmentTree(a);

    while(m + k --) {
        ll a, b, c, d;
        cin >> a >> b >> c;

        if(a & 1) {
            cin >> d;
            lazySegmentTree.update_range(b - 1, c, d); // 구간 갱신
        }
        else {
            cout << lazySegmentTree.query(b - 1, c) << nl;
        }
    }
}