BOJ 10999 구간합 구하기 2 - 두 가지 구현

 

Range update 를 해야 하기 때문에 소위 Lazy Propagation 을 구현해야 하는데...

두 가지 다른 구현을 가지고 비교해 보기 위해 글을 쓴다. 

두 구현의 우열을 논하는 것은 아니다. 이해하기 편한 쪽을 선택하면 되겠다. 

 

구간 업데이트가 \( O(\log(n))\) 으로 동작하려면 어떻게 되어야 하는가?

(1) node 의 관리 구간이 업데이트 구간에 포함되면 더 이상 하위 노드로 재귀 호출을 해서는 안된다.

(2) 도달한 노드의 대표값은 업데이트 되어야만 한다.(그래야 상위 노드의 값도 제대로 된 값을 가지게 된다.)

 

위의 두 사항을 염두에 두고 있자.

 

1.  널리 쓰이는 구현

이제 흔히 보이는 lazy propagation 구현 코드부터 보자.

먼저 range update 를 수행하는 함수이다.

 

 

함수의 시작부분에서 일단 pending value 인 lazy[node] 를 일단 처리한다.

node 가 관리하는 구간 [ l , r ] 이 업데이트가 필요한 구간 [ ul , ur ] 에 속하는지 여부를 따지기 전에...

 

위와 같은 방식으로 구현했을 때, 마음이 조금 불편하다.

현재 구간이 업데이트 구간에 완전히 포함되는 경우 현재 구간이 아닌 자식 구간들에 pending 값이 설정되기 때문이다.

(현재 도달한 node 에 pending 값(lazy[node])이 0 이 아니면, 부모 노드가 완전히 업데이트 구간에 포함되었었다는 뜻이 된다.)

부모가 완전히 포함됐을 때, 자식이 pending 값을 갖는게 자연스럽게 느껴지지 않는다.

 

더군다나 위의 코드는 구간이 업데이트 구간에 포함되면 아래의 deal_lazy 함수를 두 번이나 호출해야 한다.

 

 

부분만 봐서는 아쉽다면 전체 코드는 다음과 같다. (검색에서 보이는 코드는 거의 대동소이했다.)

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

ll arr[1000001], tree[3000000], lazy[3000000];

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

void deal_lazy(int l, int r, int node){
    if(!lazy[node]) return;
    
    tree[node]+=(r-l+1)*lazy[node];
    if(l!=r) {
        lazy[2*node]+=lazy[node];
        lazy[2*node+1]+=lazy[node];
    }
    lazy[node]=0;
}

void upd(int l,int r,int node,int ul,int ur, ll d){
    deal_lazy(l,r,node);
    
    if(ur<l || r<ul) return;   
    if(ul<=l && r<=ur) {
        lazy[node]+=d;
        deal_lazy(l,r,node);
        return;
    }
    
    int mid=l+r>>1;
    upd(l,mid,2*node,ul,ur,d);
    upd(mid+1,r,2*node+1,ul,ur,d);
    tree[node]=tree[2*node]+tree[2*node+1];
}

ll qry(int l,int r,int node, int ql,int qr){
    deal_lazy(l,r,node);
    
    if(qr<l || r<ql) return 0;
    if(ql<=l && r<=qr) return tree[node];
    
    int mid=l+r>>1;
    return qry(l,mid,2*node,ql,qr)+qry(mid+1,r,2*node+1,ql,qr);
}

int main(){
    int n,m,k; scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%lld", &arr[i]);
    init(1,n, 1);
    
    for(int i=0;i<m+k;i++){
        int op; scanf("%d",&op);
        if(op==1){
            int a,b; ll d;
            scanf("%d%d%lld",&a,&b,&d);
            upd(1,n, 1, a,b, d);
        } else {
            int a,b; scanf("%d%d", &a,&b);
            printf("%lld\n", qry(1,n,1,a,b));
        }
    }
}

 

2. 변화를 준 구현

앞서 마음이 불편하다는 표현을 쓴 바 있다. 원하는 바는 다음과 같다.

(1) pending 값을 자식 구간이 아니라 현재 구간에 설정하고 싶다.

(2) 어떤 경우이든 deal_lazy 에 해당하는 함수가 한 번만 호출되게 하고 싶다.

 

이런 요구에 따른 내 구현은 다음과 같다.

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

ll arr[1000001],tree[3000000], pending[3000000];

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

void propagation(int l, int r, int node){
    if(pending[node]==0) return;
    
    ll v=pending[node];
    int mid=l+r>>1;
    tree[2*node]+=(mid-l+1)*v, tree[2*node+1]+=(r-mid)*v;
    pending[2*node]+=v, pending[2*node+1]+=v;
    pending[node]=0;
}

void upd(int l, int r, int node, int ul, int ur, ll d){
    if(ur<l || r<ul) return;
    if(ul<=l && r<=ur) {
        tree[node]+=d*(r-l+1);
        if(l!=r)pending[node]+=d;
        return;
    }
    
    propagation(l,r,node);
    int mid=l+r>>1;
    upd(l,mid,2*node,ul,ur,d), upd(mid+1,r,2*node+1,ul,ur,d);
    tree[node]=tree[2*node]+tree[2*node+1];
}

ll qry(int l,int r, int node, int ql, int qr){
    if(qr<l || r<ql) return 0;
    if(ql<=l && r<=qr) return tree[node];
    
    propagation(l,r,node);
    int mid=l+r>>1;
    return qry(l,mid,2*node,ql,qr)+qry(mid+1,r,2*node+1,ql,qr);
}

int main(){
    int n,m,k; scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%lld", &arr[i]);
    init(1,n,1);
    
    for(int i=0;i<m+k;i++){
        int op; scanf("%d", &op);
        
        if(op==1){
            int l,r; ll d; scanf("%d%d%lld",&l,&r,&d);
            upd(1,n,1,l,r,d);
        } else {
            int l,r; scanf("%d%d",&l,&r);
            printf("%lld\n", qry(1,n,1,l,r));
        }
    }
}

 

앞선 구현의 update 함수와 달라진 update 함수는 다음과 같다.

 

 

보는 바와 같이 시작 부분에서 pending value를 처리하지 않고, 구간이 업데이트 구간에 포함된 경우에만 pending 값을 수정한다.

그리고 propagation(앞선 코드에서는 deal_lazy에 해당)은 하위 노드로 진행해야 할 때 1번만 호출된다.

query 함수도 시작부분에서 propagtion 을 하지 않아도 된다.

 

이렇게 이해하기 쉬워진(적어도 내 기준에는!) 반면에 propagation 함수 내부는 조금 복잡하다.

 

 

두 구현의 차이는 pending[node](혹은 lazy[node]) 의 의미를 파악하면 쉽게 이해할 수 있다.

 

첫 번째 구현에서 pending[node] 가 0 이 아닌 것의 의미는

"제 부모가 업데이트 구간에 완전히 포함되어서 업데이트 함수가 종료되어 전 아직 처리가 완전히 되지 않았어요!"

이다. 

 

두 번째 구현에서는,

"난 완전히 업데이트 구간에 속해서 여기서 업데이트를 종료하는데, 내 자식들은 처리가 아직 끝나지 않았다오!"

가 되겠다.