[알고개념] 7. Lazy Propagation

이 글은 백준에서 제공하는 공식 북을 참고하였습니다. https://book.acmicpc.net/ds/segment-tree-lazy-propagation

 

1. Lazy Propagation

기존 세그먼트 트리에서 하나의 값을 업데이트하는 것은 쉽게 가능했다. 리프 노드의 값을 업데이트한 후 그 부모들을 따라가서 업데이트만 해주면 되기 때문이다. 그러나 하나의 값이 아닌 "구간의 값을 변경"하는 경우에는 단순히 update 함수를 여러번 반복하기만 할 경우 무조건 시간초과가 난다. 대표적으로 https://www.acmicpc.net/problem/10999 이 문제를 보면 100만개의 수에 대해서 구간이 총 10000번 변할 수 있는데 하나하나 업데이트를 하면 최악의 경우 1000억번 update 함수를 실행해야 한다. 따라서 이 문제를 해결하기 위해서는 세그먼트 트리를 Lazy Propagation (느리게 갱신) 하는 기법을 사용해야 한다. 

void update_lazy(vector<long long> &tree, vector<long long> &lazy, int node, int start, int end) {
    if (lazy[node] != 0) {
        tree[node] += (end-start+1)*lazy[node];
        if (start != end) {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
}

void update_range(vector<long long> &tree, vector<long long> &lazy, int node, int start, int end, int left, int right, long long diff) {
    update_lazy(tree, lazy, node, start, end);
    if (left > end || right < start) {
        return;
    }
    if (left <= start && end <= right) {
        tree[node] += (end-start+1)*diff;
        if (start != end) {
            lazy[node*2] += diff;
            lazy[node*2+1] += diff;
        }
        return;
    }
    update_range(tree, lazy, node*2, start, (start+end)/2, left, right, diff);
    update_range(tree, lazy, node*2+1, (start+end)/2+1, end, left, right, diff);
    tree[node] = tree[node*2] + tree[node*2+1];
}