📗 레이지 세그 배우기

1. Lazy propagation 세그먼트 트리의 목적

세그먼트 트리는 원소 하나의 값 바꾸기, 구간의 누적합 구하기가 모두 $O(\log N)$에 가능했다.

<aside> ❓

만약 특정 구간의 모든 원소의 값을 바꾸려면 어떻게 해야할까?

</aside>

기본 세그먼트 트리에서는 구간 내의 모든 원소의 값을 변경하려면 일일이 쿼리를 날려서 변경해야 하기 때문에 $O(N\log N)$이 걸린다.

구간 쿼리를 $O(\log N)$에 처리할 수 있도록 하는게 Lazy propagation 세그먼트 트리이다.

쿼리가 업데이트한 내용을 모든 노드에 업데이트 하지 않고 누적하고 있다가 노드의 값이 필요할 때 업데이트를 진행하고 값을 가저오는 것이 기본 아이디어이다.

2. 구조

세그먼트 트리와 기본 구조가 같다. 여기에 lazy 배열이 추가 된다.

일반 세그먼트 트리의 노드들이 lazy라는 또 다른 저장공간을 갖고 있는 것이다.

lazy 배열: 현재 노드 전체에 값에 적용되는 업데이트 내용을 담고 있는 배열

업데이트 쿼리를 받자마자 리프노드까지 내려가서 업데이트 하는 것이 아니라 lazy 배열에 저장하고 있다가 노드에 직접 접근할 일이 생길 때 lazy를 밑으로 전파하며 부분적인 업데이트를 진행한다.

3. 구현

class Seg
{
    private:
        int n;
        vector<ll> tree;
        vector<ll> lazy;

        void prop(int node, int start, int end)
        {
            if(lazy[node] == 0) return;
            tree[node] += lazy[node] * (end-start+1);
            if(start != end){
                lazy[2*node] += lazy[node];
                lazy[2*node+1] += lazy[node];
            }            
            lazy[node] = 0;
        }

        void upd(int node, int start, int end, int left, int right, ll val)
        {
            prop(node, start, end);
            if(right<start || end<left) return;
            if(left<=start && end<=right){
                lazy[node] += val;
                prop(node, start, end);
                return;
            }

            int mid = start+end>>1;
            upd(2*node, start, mid, left, right, val);
            upd(2*node+1, mid+1, end, left, right, val);

            tree[node] = tree[2*node]+tree[2*node+1];
        }

        ll qry(int node, int start, int end, int left, int right)
        {
            prop(node, start, end);
            if(right<start || end<left) return 0;
            if(left<=start && end<=right) return tree[node];

            int mid = start+end>>1;
            ll l = qry(2*node, start, mid, left, right);
            ll r = qry(2*node+1, mid+1, end, left, right);

            return l+r;
        }

    public:
        Seg(int n): n(n)
        {
            tree.resize(4*n);
            lazy.resize(4*n);
        }

        void upd(int left, int right, ll val) {upd(1, 1, n, left, right, val);}
        ll qry(int left, int right) {return qry(1, 1, n, left, right);}
};

일반 세그먼트 트리와 비슷하게 구현하고 prop함수가 추가된다.

특정 노드에 도달 할 때마다 prop함수를 통해 업데이트를 진행한 후 값을 가져오는 것이다.

다음은 구현할 때 조심해야 할 것들이다.