[C++] 10999 - 구간 합 구하기 2 (플래티넘4)

1. 문제 설명

 

10999번: 구간 합 구하기 2

---

2. 아이디어

Lazy Propagation(게으른 전파)라는 알고리즘을 처음 접했던 문제였는데 진짜 신박하고 재밌는 알고리즘이었다.

세그먼트 트리(Segment Tree)에 대한 선행 지식이 필요하지만, 난 따로 포스팅을 해놓은게 없다..(곧 할 거다 ㅠ)

여긴 아이디어를 작성하는 곳이지 알고리즘을 설명하는 목적은 아니니까 자세한 내용은 따로 다룰 것이다.

 

Lazy Propagation of Segment Tree는 직역 그대로 느리게 갱신되는 세그먼트 트리이다.

문제 조건에서 '중간에 수의 변경이 빈번히 일어나고'와 '중간에 어떤 부분의 합을 구하려 한다.' 라는 문장이

해당 알고리즘을 사용하라는 숨은 의도가 아니었을까 싶다.

 

구간에 대한 연산을 사용하기 위해 세그먼트 트리 자료구조를 사용하는 건 대부분 아는 사실이지만,

하나의 값을 업데이트 하는데 걸리는 시간이 logN이고 구간 최댓값이 N이면

해당 자료구조를 구간으로 업데이트하라고 주어진다면 최대 O(NlogN)의 시간이 소모된다.

문제는 이번 조건이  N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 라는 점이다.

한 번이면 몰라도 최악의 경우의 업데이트를 10,000번 수행하면 무조건 타임 에러가 난다.

 

그래서 한 가지 꼼수를 사용하는 것이다. 업데이트가 필요하면 당장 업데이트를 하는 게 아니라

"지금 하긴 좀 귀찮은데, 기억해 둘 테니까 업데이트는 나중에 할게~! 지금은 안 할거야!"라고

연산을 미루는 알고리즘이다. 진짜 신기하지 않나??? 또 나만 즐겁나..

 

여튼 빠른 시일내에 나머지 문제도 전부 포스팅하면 알고리즘 파트를 정리할 테니 그때 자세히 설명해야겠다.

 

---

3. 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <cmath>

#define endl "\n";
using namespace std;

long long arr[1000010];
vector<long long> Lazy;  // Lazy Propagation 기억 장치
vector<long long> SegTree;
vector<tuple<int, int, int, long long>> Ctrl;

void inputInfo(int* n, int* m, int* k) {
    cin >> *n >> *m >> *k;
    for (int i=0; i<*n; i++) cin >> arr[i];
    for (int i=0; i<*m+*k; i++) {
        int a, b, c; 
        long long d;

        cin >> a;
        if (a == 1) {
            cin >> b >> c >> d;
            Ctrl.push_back({a, b, c, d});
        } else {
            cin >> b >> c;
            Ctrl.push_back({a, b, c, -1});
        }
    }
}

int calc_size_tree(int n) {
    int height = (int)ceil(log2(n));
    int size = (1 << (height + 1));

    return size;
}

long long create_tree(int left, int right, int idx) {
    if (left == right) return SegTree[idx] = arr[left];
    
    int mid;
    mid = (left + right) / 2;
    SegTree[idx] = create_tree(left, mid, idx*2+1) + create_tree(mid+1, right, idx*2+2);
    return SegTree[idx];
}

void lazyUpdate(int idx, int start, int end) {
    if (Lazy[idx] != 0) {
        SegTree[idx] += (end - start + 1) * Lazy[idx];
        if (start != end) {
            Lazy[idx * 2 + 1] += Lazy[idx];
            Lazy[idx * 2 + 2] += Lazy[idx];
        }
        Lazy[idx] = 0;
    }
}

void updateTree(int start, int end, int idx, int left, int right, long long value) {
    lazyUpdate(idx, start, end);
    
    if (right < start || end < left) return; // exception handling
    if (left <= start && end <= right) { // lazy propagation에서는 인덱스가 넘어가는 순간 업데이트 진행. 그 전까진 보류한다.
        SegTree[idx] += (end - start + 1) * value;
        if (start != end) {
            Lazy[idx * 2 + 1] += value;
            Lazy[idx * 2 + 2] += value;
        }
        return;
    }

    int mid = (start + end) / 2;
    updateTree(start, mid, idx*2+1, left, right, value);
    updateTree(mid+1, end, idx*2+2, left, right, value);
    SegTree[idx] = SegTree[idx * 2 + 1] + SegTree[idx * 2 + 2];
}

long long Query(int start, int end, int idx, int left, int right) {
    lazyUpdate(idx, start, end);

    if (right < start || end < left) return 0; // exception handling
    if (left <= start && end <= right) return SegTree[idx];

    int mid = (start + end) / 2;
    long long left_value = Query(start, mid, idx*2+1, left, right);
    long long right_value = Query(mid+1, end, idx*2+2, left, right);
    return left_value + right_value;
}

void solution(int n, int m, int k) {
    int flag, left, right; 
    for (int i=0; i < m+k; i++) {
        flag = get<0>(Ctrl[i]);
        left = get<1>(Ctrl[i]) - 1;
        right = get<2>(Ctrl[i]) - 1;

        if (flag == 1) {
            long long value = get<3>(Ctrl[i]);
            updateTree(0, n-1, 0, left, right, value);
        } else {
            cout << Query(0, n-1, 0, left, right) << endl;
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, k;
    inputInfo(&n, &m, &k);

    int treeSize = calc_size_tree(n);
    SegTree.resize(treeSize);
    Lazy.resize(treeSize);
    create_tree(0, n-1, 0);

    solution(n, m, k);

    return 0;
}