[자료구조] Lazy Propagation

세그먼트 트리 : latter2005.tistory.com/28?category=946518

[자료구조] 세그먼트 트리

세그먼트 트리에서 자주 업데이트가 발생할 때 이를 더욱 효율적으로 처리하기 위한 알고리즘입니다.

간단하게 설명하자면 구간 a~b의 값을 변경할 때 모든 트리구조, 배열을 변경하지 않고 접근 시 차근차근 변경해 나가겠다는 의미입니다.

 

예시를 들어 설명하도록 하겠습니다.

ary = {0, 1, 2, 3, 4, 5, 6, 7}

먼저 세그먼트 트리로 작성하면 다음과 같습니다.

기존 세그먼트 트리에서 구간 0~3에 각각 1을 더하고 구간합을 구하기 위해서는 0, 1, 2, 3번 인덱스까지 접근을 하고 값을 변경해준 후 트리에 반영하기까지 많은 작업을 필요로 합니다.

기존 세그먼트 트리

이 작업들을 최소화하기 위해서 사용하는 것이 Lazy Propagation 알고리즘입니다.

트리 외에 Lazy 변수를 추가하여 이들이 갱신해야 할 값들이 남아 있다는 것을 알려주고, 다음 접근 시 갱신, 자식들에게 전파해 나갑니다.

마찬가지로 구간 0~3에 1을 더해보겠습니다.

구간 0~3에 각각 +1

구간에 맞는 노드와 상위 노드만 갱신을 하며 0~3 구간에 4를 더하고 자식들에게 lazy값 1을 기록 해 둡니다. 그 후 상위 노드는 자식들을 더해 갱신합니다.

자식들에게 lazy 기록 : lazy[node << 1] += qury_diff;  lazy[(node << 1) + 1] += qury_diff;

자식 노드 값들을 더함 : tree[node] = tree[node << 1] + tree[(node << 1) + 1];

 

이번에는 구간 0~2에 1을 더 더해보도록 하겠습니다.

구간 0~2에 +1

구간 0~1에 해당하는 노드는 접근을 하지 않았으므로 lazy값을 1을 추가해 2가 됩니다.

구간 2~3에서 2의 값을 +1 해 주어야 하므로 2~3 노드에 접근하게 되면 남아있는 lazy값 1과 현재 더해야 할 1을 함께 갱신하게 되며 lazy는 자식이 2개이므로 2, 현재 더하는 구간은 2이므로 1, 총 3을 더하게 됩니다.

그 후 자식들은 lazy를 사용하지 않고 바로 갱신합니다.

이러한 과정은 update 외 query에서도 일어나며 이때는 남아있는 lazy 값들을 반영만 하게 됩니다.

 

코드

클래스와 템플릿을 사용해서 기본 연산자가 사용 가능한 int, long, double 형 등을 사용할 수 있게 만들었습니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
template <typename T>
class segment_tree {
private:
    vector<T> tree;
    vector<T> lazy;
    /*
    H : log(N)(올림)
    8 -> 3, 2^4-1 = 15
    9 -> 4, 2^5-1 = 31
    node 개수 : 2^(H+1) -> 0번 인덱스는 사용하지 않음
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (h+1));
    */
    int ary_size, h, tree_size;
    int qury_left, qury_right;
    T qury_diff;
    T init(T ary[], int node, int start, int end) {
        if (start == end) {
            return tree[node] = ary[start];
        }
        else {
            return tree[node] = init(ary, node << 1, start, (start + end) >> 1) +
                init(ary, (node << 1) + 1, ((start + end) >> 1) + 1, end);
        }
    }
    T init(vector<T> &ary, int node, int start, int end) {
        if (start == end) {
            return tree[node] = ary[start];
        }
        else {
            return tree[node] = init(ary, node << 1, start, (start + end) >> 1) +
                                init(ary, (node << 1) + 1, ((start + end) >> 1) + 1, end);
        }
    }
    void _update_lazy(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += (end - start + 1)*lazy[node];
            // leaf가 아니면
            if (start != end) {
                lazy[node << 1] += lazy[node];
                lazy[(node << 1) + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
    void _update_range(int node, int start, int end) {
        _update_lazy(node, start, end);//lazy값 반영
        if (qury_left > end || qury_right < start) {
            return;
        }
        if (qury_left <= start && end <= qury_right) {
            tree[node] += (end - start + 1)*qury_diff;//현재 노드 갱신
            if (start != end) {
                lazy[node << 1] += qury_diff;//자식 전파
                lazy[(node << 1) + 1] += qury_diff;
            }
            return;
        }
        _update_range(node << 1, start, (start + end) >> 1);
        _update_range((node << 1) + 1, ((start + end) >> 1) + 1, end);
        tree[node] = tree[node << 1] + tree[(node << 1) + 1];
    }
    T _sum(int node, int start, int end) {
        _update_lazy(node, start, end);//lazy값 반영
        if (qury_left > end || qury_right < start) {
            return 0;
        }
        if (qury_left <= start && end <= qury_right) {
            return tree[node];
        }
        return _sum(node << 1, start, (start + end) >> 1) + 
            _sum((node << 1) + 1, ((start + end) >> 1) + 1, end);
    }
public:
    segment_tree(T ary[], int size) :ary_size(size) {
        h = (int)ceil(log2(size));
        tree_size = (1 << (h + 1));
        tree.resize(tree_size);
        lazy.resize(tree_size);
        init(ary, 1, 0, size - 1);
    }
    segment_tree(vector<T> &ary) : ary_size(ary.size()){
        h = (int)ceil(log2(ary.size()));
        tree_size = (1 << (h + 1));
        tree.resize(tree_size);
        lazy.resize(tree_size);
        init(ary, 1, 0, ary.size() - 1);
    }
    segment_tree(vector<T> &ary, int start, int end) : ary_size(end-start+1) {
        h = (int)ceil(log2(end - start + 1));
        tree_size = (1 << (h + 1)) - 1;
        tree.resize(tree_size);
        lazy.resize(tree_size);
        init(ary, 1, start, end);
    }
    void update_range(int left, int right, T diff) {
        qury_left = left;
        qury_right = right;
        qury_diff = diff;
        _update_range(1, 0, ary_size - 1);
    }
    T qury(int left, int right) {
        qury_left = left;
        qury_right = right;
        return _sum(1, 0, ary_size-1);
    }
};
 
int solution(vector<int> arr) {
    int answer = 1;
    segment_tree<int> tree(arr);
    tree.update_range(0, 3, 1);
    tree.update_range(0, 2, 1);
    return tree.qury(0 ,7);
}
 
int main() {
    vector<int> arr = { 0, 1, 2, 3, 4, 5, 6, 7};
    printf("%d", solution(arr));
}