[C++ 알고리즘] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation of Segment Tree)

우리는 세그먼트 트리를 이용하여 다음과 같은 쿼리 문제를 풀이할 수 있었습니다.

→ 하나의 데이터 갱신과 구간의 대푯값 구하기 (반대로 구간의 데이터 갱신과 점의 대푯값 구하기도 가능합니다.)

 

그렇다면 구간의 데이터 갱신과 구간의 대푯값을 구하는 쿼리들을 기존의 세그먼트 트리를 사용해도 O(Q log N) 시간에 해결할 수 있을까요?

답은 불가능하다입니다. (자세한 이유는 아래의 접은 글↓에 정리되어 있습니다.)

예를 들어 백준(BOJ)의 10999번 문제 '구간 합 구하기 2' 문제를 다음과 같이 세그먼트 트리로 구현했다고 가정합시다.

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> v, tree;

int init(int n, int b, int e) {
    if(b == e) return tree[n] = v[b];

    int l = init(n*2, b, (b+e)/2);
    int r = init(n*2 + 1, (b+e)/2 + 1, e);

    return tree[n] = l + r;
}

void update(int n, int b, int e, int idx, int diff) {
    if(idx < b || e < idx) return;

    tree[n] += diff;

    if(b < e) {
        update(n*2, b, (b+e)/2, idx, diff);
        update(n*2 + 1, (b+e)/2 + 1, e, idx, diff);
    }
}

int f(int n, int b, int e, int l, int r) {
    if(r < b || e < l) return 0;
    if(l <= b && e <= r) return tree[n];

    return f(n*2, b, (b+e)/2, l, r) + f(n*2 + 1, (b+e)/2 + 1, e, l, r);
}

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

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

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

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

    M += K;
    while(M--) {
        int Q, a, b; cin >> Q >> a >> b;

        if(Q == 1) {
            int diff = b - v[a];
            v[a] = b;
            update(1, 1, N, a, diff);
        }
        else if(Q == 2) cout << f(1, 1, N, a, b) << "\n";
    }
}

 

그러면 구간의 모든 원소에 대해 특정 값을 더해주는 쿼리에 대해 update 함수에 대한 '최초' 호출이 최대 N번 발생하게 됩니다.

그러면 하나의 쿼리에 대해 O(N log N)이라는 시간이 발생하게 되고 따라서 문제에 대한 전체 시간 복잡도는 O(QN log N)으로 시간 초과가 발생할 수 있습니다.

따라서 이 문제를 일반적인 세그먼트 트리로 풀이하는 것은 불가능합니다.

우리는 이러한 유형의 문제를 풀이하기 위해 느리게 갱신되는 세그먼트 트리(Lazy Propagation of Segment Tree)를 사용해야 합니다.

 

예제 하나를 풀어보면서 정리해봅시다.

 

 

백준 BOJ 10999번 : 구간 합 구하기 2

10999번: 구간 합 구하기 2

난이도 : Platinum IV

알고리즘 분류 : 느리게 갱신되는 세그먼트 트리

 

 

 

1번 쿼리에 대해서는 구간 전체의 원소 각각에 diff만큼의 값을 더해주고, 2번 쿼리에 대해서는 구간 전체 원소들의 합을 구해서 출력해주어야 하는 문제입니다.

이처럼 구간에 대한 업데이트와 구간에 대한 대푯값을 동시에 처리해야 하는 문제에 대해 느리게 갱신되는 세그먼트 트리를 활용하여 문제를 풀이할 수 있습니다.

 

트리를 하나 더 선언하여, 이 트리에는 하위 노드가 호출 되었을 때 업데이트 할 값만 전파해주도록 하는 것입니다. (이러한 트리를 예를 들어 임시적으로 lazy tree라고 합시다.)

 

 

 

위와 같이 특정 구간에 해당하는 노드가 호출되었을 때에만 lazy tree의 해당 노드에서 자식 노드로 1단계만 값을 전파해줍니다.

lazy tree의 갱신은 구간의 값을 갱신할 때와 구간의 대푯값을 구하는 경우 모두 재귀적으로 호출이 되어야 합니다.

이렇게 처리할 경우 (물론 lazy tree말고 segment tree 역시 동시에 갱신이 되며,) 두 경우 모두 O(log N) 시간에 처리할 수 있습니다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> v, u, w; // v : array, u : tree, w : lazy

int init(int n, int b, int e) {
    if(b == e) return u[n] = v[b];

    int lv = init(n*2, b, (b+e)/2);
    int rv = init(n*2 + 1, (b+e)/2 + 1, e);

    return u[n] = lv + rv;
}

void lazy(int n, int b, int e) {
    if(w[n] == 0) return;

    u[n] += (e-b+1)*w[n];

    if(b != e) {
        w[n*2] += w[n];
        w[n*2 + 1] += w[n];
    }

    w[n] = 0;
}

int upd(int n, int b, int  e, int l, int r, int diff) {
    lazy(n, b, e);

    if(r < b || e < l) return u[n];

    if(l <= b && e <= r) {
        w[n] += diff;
        lazy(n, b, e);
        return u[n];
    }

    int lv = upd(n*2, b, (b+e)/2, l, r, diff);
    int rv = upd(n*2 + 1, (b+e)/2 + 1, e, l, r, diff);

    return u[n] = lv + rv;
}

int query(int n, int b, int e, int l, int r) {
    lazy(n, b, e);

    if(r < b || e < l) return 0;
    if(l <= b && e <= r) return u[n];

    int lv = query(n*2, b, (b+e)/2, l, r);
    int rv = query(n*2 + 1, (b+e)/2 + 1, e, l, r);

    return lv + rv;
}

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

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

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

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

    w.resize(N*4);

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

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

 

구현은 위와 같이 해줄 수 있습니다.

v 벡터가 원래 값을 저장하는 배열, u 벡터가 세그먼트 트리, w 벡터가 propagation 값을 저장하는 lazy 트리에 해당합니다.

 

구간에 값을 더해주는 경우, upd 함수에서 기존 세그먼트 트리의 갱신 이전에 lazy tree의 노드들의 값을 동시에 전파시키면서 값을 업데이트 해줌을 확인할 수 있습니다.

 

구간의 합을 구하는 경우에도 특정 구간에 포함되는 노드들의 값을 재귀적으로 더하기 이전에 lazy tree 노드들의 값을 먼저 전파시켜 내려가면서 합을 구해줌을 확인할 수 있습니다.