Segment with Lazy Propagation

Lazy Propagation

세그먼트 트리에서 구간을 업데이트 할때, 해당하는 모든 노드를 업데이트 해주는것은 최대 O(nlgn) 만큼 시간이 걸리는데 Lazy Propagation을 사용하면 O(lgn) 시간안에 업데이트를 할수 있습니다.

이를 위해 lazy라는 배열이 필요하고, lazy에는 해당 idx에 해당하는 트리의 노드에 업데이트 되어야 할 값이 들어가게 됩니다.

 

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

10999번: 구간 합 구하기 2

 

//10999 - 구간 합 구하기 2
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M, K;
vector<long long> arr;
 
struct SegTreeLP
{
    int n;
    vector<long long> tree, lazy;
 
    SegTreeLP(vector<long long> &arr, int n) : n(n), tree(n * 4), lazy(n * 4, 0)
    {
        init(arr, 0, n - 1, 1);
    }
 
    long long init(vector<long long> &arr, int left, int right, int node)
    {
        if (left == right)
            return tree[node] = arr[left];
        int mid = (left + right) / 2;
        return tree[node] = init(arr, left, mid, node * 2) + init(arr, mid + 1, right, node * 2 + 1);
    }
 
    void update_lazy(int node, int nodeLeft, int nodeRight)
    {
        if (lazy[node] != 0)
        {
            tree[node] += lazy[node] * (nodeRight - nodeLeft + 1);
            if (nodeLeft != nodeRight)
            {
                lazy[node * 2] += lazy[node];
                lazy[node * 2 + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
 
    long long query(int left, int right, int node, int nodeLeft, int nodeRight)
    {
        update_lazy(node, nodeLeft, nodeRight);
        if (right < nodeLeft || nodeRight < left)
            return 0;
        if (left <= nodeLeft && nodeRight <= right)
            return tree[node];
        int mid = (nodeLeft + nodeRight) / 2;
        return query(left, right, node * 2, nodeLeft, mid) + query(left, right, node * 2 + 1, mid + 1, nodeRight);
    }
 
    long long query(int left, int right)
    {
        return query(left, right, 1, 0, n - 1);
    }
 
    void update(int left, int right, long long diff, int node, int nodeLeft, int nodeRight)
    {
        update_lazy(node, nodeLeft, nodeRight);
        if (right < nodeLeft || nodeRight < left)
            return;
        if (left <= nodeLeft && nodeRight <= right)
        {
            lazy[node] += diff;
            update_lazy(node, nodeLeft, nodeRight);
            return;
        }
        int mid = (nodeLeft + nodeRight) / 2;
        update(left, right, diff, node * 2, nodeLeft, mid);
        update(left, right, diff, node * 2 + 1, mid + 1, nodeRight);
        tree[node] = (tree[node * 2] + tree[node * 2 + 1]);
    }
 
    void update(int left, int right, long long diff)
    {
        update(left, right, diff, 1, 0, n - 1);
    }
};
 
void init()
{
    cin >> N >> M >> K;
    arr = vector<long long>(N);
    for (int i = 0; i < N; ++i)
        cin >> arr[i];
}
 
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    SegTreeLP stlp(arr, N);
    int flag, x, y;
    long long r;
    M += K;
    for (int i = 0; i < M; ++i)
    {
        cin >> flag;
        cin >> x >> y;
        if (flag == 1)
        {
            cin >> r;
            stlp.update(x - 1, y - 1, r);
        }
        else
            cout << stlp.query(x - 1, y - 1) << "\n";
    }
}

위 문제가 lazy propagation을 사용해야 풀리는 문제입니다.

update_lazy라는 함수가 새로 추가되어 인자값으로 전달되는 노드의 lazy값을 현재 노드에 적용하고 자식들에게 전파하는 역할을 수행합니다.

구간의 합을 구하는 쿼리에서는 재귀함수가 호출될때 마다 처음에 한번 사용해주어, 현재 노드의 값에 lazy를 적용해 알맞은 값으로 바꾸어주고, 자식들에게 그 lazy값을 전파합니다.

값을 업데이트 해주는 쿼리에서도 마찬가지로 lazy_update를 처음에 호출하여 기존 lazy값들을 현재노드에 적용하고 자식노드에 전파합니다. 모든 구간이 업데이트해야되는 구간안에 포함되는 기저상태에 도달하게 되면, diff값을 적용하고 update_lazy를 호출하여 diff를 자식들에게 전파합니다. 그 이후엔 함수들이 반환되면서 바뀐 자식노드들의 합으로 부모노드를 갱신시킵니다.