[C/C++] 백준 10999번 - 구간 합 구하기 2

✏️ 문제 링크

https://www.acmicpc.net/problem/10999

10999번: 구간 합 구하기 2

 

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

세그먼트 트리의 한 종류인 느리게 갱신되는 세그먼트 트리를 구현하는 문제입니다.

구간에다가 특정 값을 더하게 되는 연산을 하게되면 일반적인 세그먼트 트리로 구현하게 되면 시간초과가

발생하게 됩니다. 이를 해결하기 위해 만들어진게 느리게 갱신되는 세그먼트 트리입니다.

특정 구간에 값을 더하라고 할 때, 한 개씩 다 더해주면서 구간의 값들을 갱신하는 것이 아니라

갱신이 필요한 노드들을 먼저 갱신해줘서 값을 바꿔준 뒤 나중에 바꾸고자 하는 구간들의 리프 노드들의 값을 변경합니다.

https://book.acmicpc.net/ds/segment-tree-lazy-propagation

느리게 갱신되는 세그먼트 트리

백준 북에서 자세히 설명하고 있으니 여길 참고하시길 바랍니다.

 

✏️ 문제 코드

#include<iostream>
#include<vector>
#define int long long
using namespace std;

vector<int> arr, tree, lazy; 

int init(int node, int start, int end) {
    if (start == end) 
        return tree[node] = arr[start];

    int leftSum = init(node * 2, start, (start + end) / 2);
    int rightSum = init(node * 2 + 1, (start + end) / 2 + 1, end);

    return tree[node] = leftSum + rightSum;
}

void lazyUpdate(int node, int start, int end) {
    if (lazy[node] == 0) 
        return;

    tree[node] += (end - start + 1) * lazy[node];

    if (start != end) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }

    lazy[node] = 0;
}

int updateTree(int node, int start, int  end, int l, int r, int diff) {
    lazyUpdate(node, start, end);

    if (r < start || end < l) return tree[node];

    if (l <= start && end <= r) {
        lazy[node] += diff;
        lazyUpdate(node, start, end);
        return tree[node];
    }

    int leftTree = updateTree(node * 2, start, (start + end) / 2, l, r, diff);
    int rightTree = updateTree(node * 2 + 1, (start + end) / 2 + 1, end, l, r, diff);

    return tree[node] = leftTree + rightTree;
}

int findSum(int node, int start, int end, int l, int r) {
    lazyUpdate(node, start, end);

    if (r < start || end < l) 
        return 0;
    if (l <= start && end <= r) 
        return tree[node];

    int leftTree = findSum(node * 2, start, (start + end) / 2, l, r);
    int rightTree = findSum(node * 2 + 1, (start + end) / 2 + 1, end, l, r);

    return leftTree + rightTree;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M, K; 
    cin >> N >> M >> K;

    arr.resize(N + 1);
    for (int i = 1; i <= N; i++)
        cin >> arr[i];

    tree.resize(N * 4);
    init(1, 1, N);

    lazy.resize(N * 4);

    M += K;
    while (M--) {
        int query; 
        cin >> query;

        if (query == 1) {
            int a, b, c; 
            cin >> a >> b >> c;
            updateTree(1, 1, N, a, b, c);
        }
        else if (query == 2) {
            int a, b; 
            cin >> a >> b;
            cout << findSum(1, 1, N, a, b) << "\n";
        }
    }
}