BOJ)10999 구간 합 구하기2

문제: icpc.me/10999

구간에 대한 합을 출력하는 문제이다. 그런데 쿼리중에 구간에 대한 갱신 연산을 하는 쿼리가 있다.

우리는 세그먼트 트리를 통해 구간에 대한 갱신과 합쿼리를 빠르게 처리 할 수 있지만 구간에 대한 갱신을 세그먼트 트리로만 하려고 한다면 갱신의 경우 최악의 시간복잡도는 O(NlogN)이 될것이다. 

만약 쿼리가 전부 갱신만 들어온다면 시간 복잡도는 O(N(M+K)logN)로 당연히 시간초과를 보게 될 것이다.

그래서 우리는 lazy propagation을 이용하여 구간에 대한 갱신을 조금 더 빠르게 해주는 테크닉을 이용하여 문제를 풀어야만 한다.

lazy propagation에 대한 설명은 여기에 친절하게 되어있다.

#include <cstdio>
#include <algorithm>
#define MAX_N 1000000
typedef long long ll;
using namespace std;
ll n, m, k, seg[4 * MAX_N], lazy[4 * MAX_N], a, b, c, d;
void update_lazy(ll node, ll x, ll y) {
    if (!lazy[node])
        return;
    seg[node] += (y - x + 1)*lazy[node];
    if (x != y) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}
ll update(ll lo, ll hi, ll val, ll node, ll x, ll y) {
    update_lazy(node, x, y);
    if (y < lo || hi < x)
        return seg[node];
    if (lo <= x&&y <= hi) {
        lazy[node] += val;
        update_lazy(node, x, y);
        return seg[node];
    }
    ll mid = (x + y) >> 1;
    return seg[node] = update(lo, hi, val, node * 2, x, mid) + update(lo, hi, val, node * 2 + 1, mid + 1, y);
}
ll query(ll lo, ll hi, ll node, ll x, ll y) {
    update_lazy(node, x, y);
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return seg[node];
    ll mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    scanf("%lld%lld%lld", &n, &m, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a);
        update(i, i, a, 1, 1, n);
    }
    for (int i = 0; i < m + k; i++) {
        scanf("%lld", &a);
        if (a == 1) {
            scanf("%lld%lld%lld", &b, &c, &d);
            update(b, c, d, 1, 1, n);
        }
        else {
            scanf("%lld%lld", &b, &c);
            printf("%lld\n", query(b, c, 1, 1, n));
        }
    }
    return 0;
}