문제

숫자 배열이 주어지고 구간의 합을 구하는 문제다.

단순히보면 이전의 구간합과 비슷한데 문제는 구간을 통채로 더하는 연산이 존재한다.
n이 10^6이고 구간변경이 10^4이기에 1초(약10^8)는 그냥 넘어간다.
(먼저 그렇게 제출해서 시간초과가 나왔다.)

lazy propagation

나는 세그먼트 트리 문제를 구현이 간단한 인덱스 트리로 계산한다.
세그먼트 트리는 루트 노드부터 내려오고 인덱스 트리는 리프 노드부터 올라가는 성질이 있다.

이게 왜 중요하냐면 lazy propagation 자체 개념이 구간의 합을 더할때 더할 범위까지만 오면 더이상 아래로 내려가지 않고 합을 저장해놨다가 나중에 다시 방문할때 더하기 때문이다.

예를 들어 인덱스 1~인덱스 6까지 1씩 더한다고 가정해보자.
이때 인덱스 1~인덱스 6까지 조회한다고하면 9,5,6,14 노드를 탐색할것이다. 그 아래 10,11,12,13은 조회하지 않는다.

lazy propagation에서는 update도 query와 비슷하게 방문하며 더해야할 값을 자식들만 갖고있게하는것이다.

그러고 나중에 다시 그 노드를 방문할때 갱신해줘서 사용한다.
그렇다면 구간 변경에 logn의 시작복잡도가 나오게 된다.

처음보는 개념이었기에 개념만으로는 이해가 가지않아 그림을 그려보며 절차를 따라가 보았다.

인덱스 1번부터 1~10을 저장한 그림이다. 초록색은 노드 번호다.
이를 하나씩 변경해가며 그림과 비교했더니 조금 이해가 갔다.

참조 블로그

code

#include <iostream>
using namespace std;

#ifdef _DEBUG
#define PIV (1<<4)
#else
#define PIV (1<<20)
#endif // _DEBUG
typedef long long LL;
int n, m, k;
LL tree[PIV * 2], lazy[PIV * 2];

void lazy_update(int node, int s, int e) {
    if (lazy[node] == 0) return;
    // tree update
    tree[node] += (e - s + 1) * lazy[node];
    if (s != e) {
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
    }
    lazy[node] = 0; // 더해주고나서 다시 0으로 초기화
}
void update(int node, int s, int e, int l,int r, LL val) {
    lazy_update(node, s, e); // 범위여부 상관없이 무조건 lazy_update
    if (e < l || r < s) return;
    if (l<=s && e<=r) {
        tree[node] += (e - s + 1) * val;
        if (s != e) {
            lazy[2 * node] += val;
            lazy[2 * node + 1] += val;
        }
        return;
    }
    int mid = (s + e) / 2;
    update(2 * node, s, mid, l, r, val);
    update(2 * node + 1, mid + 1, e, l, r, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}
LL query(int node, int s, int e, int l, int r) {
    lazy_update(node, s, e); // 범위여부 상관없이 무조건 lazy_update
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];
    int mid = (s + e) / 2;
    return query(2 * node, s, mid, l, r) + query(2 * node + 1, mid + 1, e, l, r);
}

void print() {
    cout << "[tree] ";
    for (int i = 1; i < 2*PIV; i++) cout <<"("<<i<<","<< tree[i]<<")"<< " ";
    cout << "\n";
    cout << "[lazy] ";
    for (int i = 1; i < 2*PIV; i++) cout << "(" << i << "," << lazy[i] << ")" << " ";
    cout << "\n\n";
}
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifdef _DEBUG
    freopen("B10999.in", "r", stdin);
#endif // _DEBUG

    cin >> n >> m >> k;
    for (int idx = 1; idx <= n; idx++) {
        int val; cin >> val;
        update(1, 1, n, idx, idx, val);
    }
#ifdef _DEBUG
    cout << "#init\n";
    print();
#endif // _DEBUG
    for (int i = 0; i < m + k; i++) {
        int a, b, c, d;
        cin >> a;
        // b,c => d
        if (a == 1) {
            cin >> b >> c >> d;
#ifdef _DEBUG
            cout << "#update " << b << "," << c << " => " << d << "\n";
#endif // _DEBUG
            update(1, 1, n, b, c, d);
#ifdef _DEBUG
            print();
#endif // _DEBUG

        }
        // query(b,c)
        else {
            cin >> b >> c;
#ifdef _DEBUG
            cout << "#query " << b << "," << c << "\nans : ";
#endif // _DEBUG
            cout << query(1, 1, n, b, c) << "\n";
#ifdef _DEBUG
            print();
#endif // _DEBUG
        }
    }
}