[백준 10999] 구간 합 구하기2

문제

www.acmicpc.net/problem/10999

 

알고리즘

lazy propagation

 

풀이

구간 갱신, 구간 쿼리를 요구하는 문제입니다.

 

일반적인 점 갱신, 구간 쿼리를 이용하는 세그먼트 트리를 활용한다면 구간 갱신을 처리할 때, 구간의 길이에 비례한 시간복잡도를 요구합니다. 하지만 lazy propagation을 활용하면 구간 갱신또한 $O(logN)$에 훌륭하게 처리가능합니다.

자세한 설명은 다른 좋은 글들이 많으니 참고 바랍니다. 구현 포인트만 짚고 마치겠습니다.

 

1. $lazy$를 업데이트 하는 것은 쿼리와 업데이트 둘 다 해당이 된다.

2. 조상노드에서 자식노드로 재귀적으로 $lazy$를 업데이트 해야한다.

3. 자식노드의 $lazy$는 조상노드를 고려해야한다.

4. 세그먼트 트리를 재귀적으로 구현 할 때, 코드에 적은 $sz*2$ 만큼 트리 크기를 만들어야만 한다.

(비재귀적인 구현은 $sz$를 찾지 않고 2*$N$으로도 해결가능하다)

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef long long ll;

int n, m, k;
vector<ll> seg;
vector<ll> lazy;
ll a, b, c, d;

void update_lazy(int node, int nl, int nr) {
    if (!lazy[node]) return;
    seg[node] += (nr - nl + 1) * lazy[node];
    if (nl != nr) {
        lazy[node << 1] += lazy[node];
        lazy[node << 1 | 1] += lazy[node];
    }
    lazy[node] = 0;
}

void range_update(int node, int nl, int nr, int ql, int qr, ll val) {
    update_lazy(node, nl, nr);
    if (nr < ql || qr < nl) return;
    if (ql <= nl && nr <= qr) {
        seg[node] += (nr - nl + 1) * val;
        if (nl != nr) {
            lazy[node << 1] += val;
            lazy[node << 1 | 1] += val;
        }
        return;
    }
    int nm = (nl + nr) / 2;
    range_update(node << 1, nl, nm, ql, qr, val);
    range_update(node << 1 | 1, nm + 1, nr, ql, qr, val);
    seg[node] = seg[node << 1] + seg[node << 1 | 1];
}

ll query(int node, int nl, int nr, int ql, int qr) {
    update_lazy(node, nl, nr);
    if (nr < ql || qr < nl) return 0;
    if (ql <= nl && nr <= qr) return seg[node];
    int nm = (nl + nr) / 2;
    return query(node << 1, nl, nm, ql, qr) + query(node << 1 | 1, nm + 1, nr, ql, qr);
}
int main() {
    FAST;
    cin >> n >> m >> k;
    
    const int sz = pow(2, ceil(log2(n)));
    seg.resize(sz << 1);lazy.resize(sz << 1);

    rep(i, n) cin >> seg[sz + i];
    for (int i = sz - 1;i > 0;--i) seg[i] = seg[i << 1] + seg[i << 1 | 1];

    rep(i, m + k) {
        cin >> a >> b >> c;
        if (a == 1) {
            cin >> d;
            range_update(1, 1, sz, b, c, d);
        }
        else {
            cout << query(1, 1, sz, b, c) << '\n';
        }
    }

    return 0;
}