Segment Tree Lazy Propagation

기본적인 세그먼트 트리는 구간에 대한 쿼리와, 특정 값을 업데이트하는 연산밖에 안된다.

만약 구간에 대해 업데이트 하는 연산이 필요하다면 Lazy Propagation 을 사용해야 한다.

 

간단한 원리는 업데이트해야하는 구간에 완전히 속한 노드들에게 lazy 값을 올려준 후, 나중에 그 노드를 방문할 때가 됬을때 lazy 값을 꺼내서 실제 값에 업데이트 해주는 방식이다.

 

*더 구체적인 설명은 https://www.acmicpc.net/blog/view/26을 참고한다.

 

struct SEG
{
    int n; vector<ll> tree, lazy;

    SEG() {}
    SEG(int n) : n(n), tree(n*4+10), lazy(n*4+10) { init(1, 1, n); }

    void init(int node, int tl, int tr)
    {
        if(tl==tr) { tree[node]=arr[tl]; return; }
        int mid=tl+tr>>1;
        init(node*2, tl, mid);
        init(node*2+1, mid+1, tr);
        tree[node]=tree[node*2]+tree[node*2+1];
    }

    void update_lazy(int node, int tl, int tr)
    {
        if(lazy[node]==0) return;
        tree[node]+=(tr-tl+1)*lazy[node];
        if(tl!=tr) { lazy[node*2]+=lazy[node]; lazy[node*2+1]+=lazy[node]; }
        lazy[node]=0;
    }

    void update(int node, int tl, int tr, int l, int r, ll dif)
    {
        update_lazy(node, tl, tr);
        if(tr<l || r<tl) return;
        if(l<=tl && tr<=r)
        {
            tree[node]+=(tr-tl+1)*dif;
            if(tl!=tr) { lazy[node*2]+=dif; lazy[node*2+1]+=dif; }
            return;
        }
        int mid=tl+tr>>1;
        update(node*2, tl, mid, l, r, dif);
        update(node*2+1, mid+1, tr, l, r, dif);
        tree[node]=tree[node*2]+tree[node*2+1];
    }

    ll query(int node, int tl, int tr, int l, int r)
    {
        update_lazy(node, tl, tr);
        if(tr<l || r<tl) return 0;
        if(l<=tl && tr<=r) return tree[node];
        int mid=tl+tr>>1;
        return query(node*2, tl, mid, l, r)+query(node*2+1, mid+1, tr, l, r);
    }

    void update(int l, int r, ll dif) { update(1, 1, n, l, r, dif); }
    ll query(int l, int r) { return query(1, 1, n, l, r); }
};

구현은 세그먼트 트리랑 거의 동일하고, update_lazy를 어떤 상황이던지 그 노드를 방문하기 전에 실행해 주어야 그 노드에 정확한 값이 들어갈 수 있다는 사실을 알 수 있다.

 

시간복잡도는 세그먼트 트리와 동일하다.

 

단순 덧셈 외의 다른 연산들에 대해 적용할 수도 있는데, 핵심은 한 구간에 같은 종류의 연산을 여러번 중복하여 적용하였을 때 연산들끼리의 덧셈 연산을 수행하고 합쳐진 하나의 연산을 구간에 대해 수행해도 문제가 없어야 한다는 것이다. 이는 연산들 사이의 순서가 의미가 있을 때도 적용할 수 있다.

 

레이지 연산을 적용할 수 있는 조건을 요약하면

1. 연산에 대한 결합 법칙이 성립한다.

2. 구간에 대한 연산이 있을 때 구간에 대한 세그먼트 트리의 값(쿼리)를 빠르게 업데이트 할 수 있어야 한다.

 

또한, 단일 업데이트가 있을 때 단순히 그쪽으로만 내려가는 것이 아니라 양쪽으로 모두 내려가야 제대로 세그먼트 트리의 값을 갱신할 수 있음에 주의하자.