Lazy Propagation 이해하기

구간 쿼리 알고리즘 중 하나인 Lazy Propagation에 대해서 알아보겠습니다.

이 글은 세그먼트 트리에 대한 개념을 알고 있다는 전제 하에 작성되었습니다.

//개인 공부용으로 작성하는 글입니다

 

일단, 구간[i, j]의 모든 값을 바꿀 수 있는 Lazy Propagation 의 작동 방식은 "업데이트를 게으르게 하는 것" 입니다.

업데이트를 필요할 때만 해서 시간 복잡도를 단축시킬 수 있는 것이라고 이해하면 될 것 같습니다.

 

구현에 대한 이해만 확실하게 한다면 어렵지 않게 사용할 수 있을 것입니다.

 

구현

이 글에서는 구간 [l, r]이 주어지면 해당 구간의 합을 구하거나, 구간 [l, r]의 모든 원소에 값 x를 더해줄 수 있는

세그먼트 트리를 구현하도록 하겠습니다.

 

1. init 함수

init 함수의 구현은 기존 세그먼트 트리의 구현과 같습니다.

배열 a[]가 주어질 때 기존 세그먼트 트리를 구축해주는 코드입니다.

vector<int> a, tree; 

int init(int start, int end, int node){ 
    if(start == end) return tree[node] = a[start]; 
    int mid = (start+end)/2; 
    return tree[node] = init(start, mid, node*2), init(mid+1, end, node*2+1); 
}

 

2. update 함수

update 함수는 update_lazy 함수와 update_range 함수로 나누어 구현합니다.

update_lazy 함수는 lazy 값을 업데이트하고 자식에게 전달하는 역할을 하며, 

update_range 함수는 기존 세그먼트 트리에서의 update 함수, 값을 업데이트 하는 역할을 합니다.

 

먼저, update_lazy 함수입니다.

lazy 값은 예전 update 때 부모로부터 전달된 값입니다.

다시 말해 어떤 노드가 관리하는 원소들에 모두 업데이트 시켜줬어야 하는 값입니다.

update_range 함수도 보고 나면 이해가 잘 될 것입니다.

 

이때 tree[node]는 start부터 end까지의 구간에 해당하는 원소의 합을 저장하고 있기 때문에

구간에 속한 원소의 수 만큼 lazy값을 더해 주고, 자식이 있다면 자식에게 lazy 값을 물려주면 됩니다.

물론 업데이트 후 lazy 값은 초기화해야겠죠.

아래는 위 설명을 그대로 코딩한 것입니다.

vector<int> lazy;

void update_lazy(int start, int end, int node)
{
    if (lazy[node] == 0) return;
       
    //lazy 값을 담당하는 원소의 수 만큼 더해주기
    tree[node] += (end - start + 1) * lazy[node];
    
    //lazy 값을 자식에게 물려주기
    if (start != end){
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
   	
    //초기화
    lazy[node] = 0;
}

 

다음으로, update_range 함수입니다.

update_range 함수는 기존 세그먼트 트리에서의 update 함수와 비슷하게 diff 값을 더해주는 역할을 합니다.

 

이 함수에서는 update_lazy 함수를 먼저 한 번 호출하여 node의 lazy 값이 존재하면 업데이트 해줍니다.

 

또한, update를 할 때 구간이 범위에 완전히 포함되는 경우에는 lazy 값을 잘 전달해 줄 수 있기 때문에

그 경우에는 tree[node]에 직접 구간에 속한 원소의 수 만큼 diff를 곱해서 더해주고 lazy 값을 자식에게 전달하지만,

구간이 범위에 걸쳐 있는 경우에는 lazy 값을 잘 전달해 줄 수가 없기 때문에

기존 세그먼트 트리의 구현과 같이 자식 노드의 return 값을 이용합니다.

void update_range(int start, int end, int node, int left, int right, int diff)
{
    update_lazy(start, end, node);
    
    //범위 밖이면 return
    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;
    }
 	
    //범위에 걸쳐 있는 경우
    int mid = (start + end) / 2;
    update_range(start, mid, node * 2, left, right, diff);
    update_range(mid + 1, end, node * 2 + 1, left, right, diff);
 
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

 

3. sum 함수

sum 함수에서는 update_lazy를 한 번 호출하고, 나머지는 기존 세그먼트 트리의 구현과 동일합니다.

int sum(int start, int end, int node, int left, int right){
    update_lazy(start, end, node);
    if (left > end || right < start) return 0;
    if (left <= start && end <= right) return tree[node];
    int mid = (start + end) / 2;
    return sum(start, mid, node * 2, left, right) + sum(mid+1, end, node*2+1, left, right);
}

 

Lazy Propagation 을 공부하기 위해서는 구현에 대한 이해가 가장 중요한 것 같습니다.