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

문제 설명

문제 링크

http://icpc.me/10999

10999번: 구간 합 구하기 2

풀이

lazy propogation 기본 문제이다.

lazy propogation은 세그먼트 트리를 응용한 구간 업데이트와 구간 쿼리를 모두 O(logN)에 할 수 있는 자료구조다. 자세한 설명은 다른 더 대단한 분들이 많이 올리셨으니 생략하겠다.

내가 참고한 글은 여기에 적어놨다.

코드

#include <cstdio>

using namespace std;
using ll = long long;

const int N = 1e6 + 6;

ll tree[4 * N], lazy[4 * N], arr[N];

void propogation(int node, int s, int e) {
    if (!lazy[node]) return;
    if (s != e) {
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
    }
    tree[node] += (e - s + 1) * lazy[node];
    lazy[node] = 0;
}

ll query(int node, int s, int e, int qs, int qe) {
    propogation(node, s, e);
    if (e < qs || qe < s) return 0;
    if (qs <= s && e <= qe) return tree[node];
    int mid = (s + e) / 2;
    return query(2 * node, s, mid, qs, qe) + query(2 * node + 1, mid + 1, e, qs, qe);
}

void update(int node, int s, int e, int qs, int qe, int k) {
    propogation(node, s, e);
    if (e < qs || qe < s) return;
    if (qs <= s && e <= qe) {
        lazy[node] += k;
        propogation(node, s, e);
        return;
    }
    int mid = (s + e) / 2;
    update(2 * node, s, mid, qs, qe, k);
    update(2 * node + 1, mid + 1, e, qs, qe, k);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

void init(int node, int s, int e) {
    if (s == e) {
        tree[node] = arr[s];
        return;
    }
    int mid = (s + e) / 2;
    init(2 * node, s, mid);
    init(2 * node + 1, mid + 1, e);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

int main() {
    int n, m, k; scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", arr + i);
    init(1, 0, N);
    for (int i = 0; i < m + k; i++) {
        int a; scanf("%d", &a);
        if (a == 1) {
            int b, c, d; scanf("%d %d %d", &b, &c, &d);
            update(1, 0, N, b, c, d);
        } else {
            int b, c; scanf("%d %d", &b, &c);
            printf("%lld\n", query(1, 0, N, b, c));
        }
    }
}