세그먼트 트리(Segment Tree) : Lazy Propagation

[선행 개념 : 세그먼트 트리]

세그먼트 트리(Segment Tree)

이전에 살펴본 세그먼트 트리에서는 트리 값의 갱신을 하나의 인덱스에 대해서만 진행했다.

예를 들어, 인덱스 5에 해당하는 노드의 값을 변경하기 위해 (1-10) -> (1-5) -> (4-5) -> (5) 구간을 거쳐오는 식이다.

칠해진 노드는 참조된 노드들이다.

하지만 우리는 한 번에 여러 개의 리프 노드에 대한 갱신이 필요할 수도 있다. 그림과 같이 4-10에 대한 구간을 한 번에 갱신하고 싶거나 할 때 말이다.

하지만 위 그림에서도 알 수 있듯 트리에서 참조된 노드의 수가 상당히 많다. 예제의 경우에는 거의 대부분의 노드가 참조되었다.

단일 리프 노드에 대한 갱신의 시간 복잡도는 O(logN)이었다.

따라서 범위 갱신에 대한 시간 복잡도는 O(NlogN)이 될 것이다. 구간의 크기만큼 리프 노드까지 내려가야 하기 때문이다. 이러한 갱신의 횟수가 많아진다면, 시간적으로 매우 비효율적이게 된다.

10999번: 구간 합 구하기 2

바로 이 문제처럼 말이다. 구간 갱신의 시간 복잡도는 O(NlogN)인데, 이러한 갱신이 M번 일어나므로

일반적인 세그먼트 트리에서 시간 복잡도는 O(MNlogN)이 된다. 따라서 문제의 시간 제한을 만족할 수 없다.

이러한 상황에서 느리게 갱신되는 세그먼트 트리(Lazy Propagation)가 효율적일 수 있다.

 

Lazy 배열

Lazy Propagation에서는 각 노드마다 lazy라는 값을 둔다.

Lazy Propagation이라는 이름에서 알 수 있듯, 이 자료구조에서는 모든 값을 그때그때 갱신하지 않는다.

굳이 갱신할 필요가 없는 노드에 대해서 lazy라는 값을 조정해 나중에 이 노드를 방문할 일이 생길 때까지는 갱신을 미루어 시간적 효율을 올리는 것이다.

 

Lazy Propagation에서의 Update (Range)

위의 예제 세그먼트 트리에 대해, 다음과 같은 갱신 요청이 들어왔을 때 동작 과정을 살펴보자.

우선 왼쪽 자식부터 살펴보자. 왼쪽 자식 노드가 나타내는 구간은 1-5로, 이는 갱신을 원하는 4-10 구간에 걸친다.

따라서, 양 자식 노드에 대해 재귀실행한다.

1-3 노드는 갱신 구간 4-10에 포함되지 않으므로, 그대로 종료된다.

4-5 노드에 주목하자. 이는 갱신 구간 4-10에 완전히 포함되는 구간이다.

이 때, Lazy Propagation은 4, 5 리프 노드를 갱신하지 않는다. 대신 이 둘이 10씩 증가됐다고 '치고' 4-5 노드의 값만 20 증가시킨다.

나중에 4, 5 리프 노드를 방문하게 될 경우 미뤄뒀던 +10 연산을 해줘야 하기 때문에, 4, 5 리프 노드에 lazy값 10을 더해준다.

다음으로 6-10 구간이다. 이 또한 갱신 구간 4-10에 완전히 포함되는 구간이므로,

6-10의 각 리프 노드들이 10씩 증가됐다고 치고 6-10 노드의 값을 50 증가시킨다.

미뤄둔 연산을 나중에 적용하기 위해 양쪽 자식에 lazy값 10을 더해놓는다.

이로써 4-10 구간에 대한 갱신 연산은 끝나게 된다.

일반적인 세그먼트 트리와 비교해 참조하는 노드의 수가 현저하게 적은 것을 확인할 수 있다.

 

이번에는 한 번 더, 다음 구간 갱신의 진행 과정을 살펴보자.

1-5구간의 노드도 참조되지만, 이 그림에서는 생략하였다.

갱신을 위한 노드 탐색 중, lazy값이 붙어 있는 노드를 만난다면 우선 그 lazy값을 현재 노드에 반영해 준다.

6-8 노드의 크기는 (8 - 6 + 1) = 3이므로, 총 30을 더해 준다. 이 값은 이전 갱신 (4-10, +10) 중에 미뤄뒀던 연산을 지금에서야 수행한 것이다.

이제 이 lazy 값을 양쪽 자식 노드에 물려준다. 다음에 이 자식 노드들을 참조했을 때, 이전에 했어야 할 연산을 수행해 주기 위함이다.

 

마찬가지로 lazy값이 붙어 있는 6-7, 8 노드도 lazy값을 노드에 반영해 준다.

lazy값을 반영한 후, 원래 갱신에 해당하는 연산을 진행해 준다.

리프 노드 8은 갱신 구간 8-9에 완전히 포함되므로, -7을 해당 노드에 바로 적용해 준다.

 

Lazy Propagation에서의 Query

Lazy Propagation에서의 쿼리는 일반적인 세그먼트 트리와 같다.

단, lazy값이 있는 노드를 탐색했을 때 그 값을 반드시 반영해 주어야 한다.

 

[코드 : BOJ 10999 구간 합 구하기 2 의 정답 코드로 대체]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
#define MAXSIZE 1000001
 
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
 
int n, m, k;
ll arr[MAXSIZE], segtree[MAXSIZE * 4], lazy[MAXSIZE * 4];
 
void create_segtree(int node, int start, int end) {
    if (start == end) {
        //리프 노드인 경우
        segtree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    create_segtree(node * 2, start, mid);
    create_segtree(node * 2 + 1, mid + 1, end);
    segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
}
 
void update_lazy(int node, int start, int end) {
    //현재 노드의 lazy값을 반영함
    if (lazy[node] != 0) {
        segtree[node] += ((ll)end - start + 1) * lazy[node];        //구간의 크기만큼 반영
        if (start != end) {
            //구간 노드라면, 양쪽 자식에 lazy값을 물려줌
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;        //초기화
    }
}
 
void update_range(int node, int start, int end, int l, int r, ll val) {
    //구간 갱신 함수
    update_lazy(node, start, end);        //방문하는 노드에 대해 lazy 값이 있다면 반영
 
    if (l > end || r < start) return;        //포함되지 않는 범위
 
    //완전히 포함되는 범위
    if (l <= start && end <= r) {
        segtree[node] += ((ll)end - start + 1) * val;    //구간의 크기만큼 '현재 노드에만' 반영
        if (start != end) {
            //구간 노드라면, 양쪽 자식에 lazy값을 추가
            lazy[node * 2] += val;
            lazy[node * 2 + 1] += val;
        }
        return;
    }
 
    //걸치는 범위
    int mid = (start + end) / 2;
    update_range(node * 2, start, mid, l, r, val);
    update_range(node * 2 + 1, mid + 1, end, l, r, val);
    segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
}
 
ll query(int node, int start, int end, int l, int r) {
    //구간 쿼리 함수
    update_lazy(node, start, end);        //방문하는 노드에 대해 lazy 값이 있다면 반영
 
    if (l > end || r < start) return 0;        //포함되지 않는 범위
 
    //완전히 포함되는 범위
    if (l <= start && end <= r) return segtree[node];
 
    //걸치는 범위
    int mid = (start + end) / 2;
    return query(node * 2, start, mid, l, r) + query(node * 2 + 1, mid + 1, end, l, r);
}
 
void init() {
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; i++) cin >> arr[i];
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    create_segtree(1, 1, n);
 
    int t, f, s, v;
    int udt = 0, qry = 0;
    while(1){
        if (udt == m && qry == k) break;
        cin >> t >> f >> s;
        if (t == 1) {
            cin >> v;
            update_range(1, 1, n, f, s, v);
            udt++;
        }
        else {
            printf("%lld\n", query(1, 1, n, f, s));
            qry++;
        }
    }
 
    return 0;
}