[Algorithm] Segment tree with Lazy propagation (BOJ 10999)

• segment tree with lazy propagation algorithm의 필요성

segment tree는 구간에 대한 query를 O(logN)에 수행할 수 있도록 한다. 한 index에 대한 update를 수행할 경우에 update의 time complexity는 역시 recursive call에 의해서 O(logN)에 수행된다. 만약 한 index가 아니라 구간 [L, R]에 대한 update를 수행할 경우 [L, R]에 속한 모든 index에 대하여 update를 해 주어야 하므로 O((R-L+1)logN), 일반적으로 쓰면 O(NlogN)의 긴 수행 시간이 필요하게 된다.

 

이를 해결하기 위해서는 일종의 optimization이 필요한데, 이것이 바로 lazy propagation이다. lazy propagation은 말 그대로 구간에 대한 update 요청이 들어와도 lazy하게 저장해 주었다가, 나중에 필요할 때가 되었을 때 propagation을 하여 tree의 node 값을 갱신하는 것이다. 이러한 방법으로 update 요청마다 들어오는 recursive call의 수를 최소한으로 줄일 수 있다. 구간 update의 time complexity도 O(logN)까지로 단축된다. 

 

 

 

• C++ implementation

tree와 lazy는 같은 크기로 선언한다.

vector<ll> tree(maxN*4), lazy(maxN*4);

 lazy propagation을 위해 update와 propagation 함수를 만들었다.

 

 

void propagation(int left, int right, int node) {
    tree[node]+=(right-left+1) * lazy[node];
    if(left!=right) {
        lazy[node*2] += lazy[node];
        lazy[node*2+1] += lazy[node];
    }
    lazy[node]=0;
 
}
 
void update(int left, int right, int node, int uleft, int uright, ll diff) {
    if(lazy[node]!=0) propagation(left,right,node);
    
    if(uright<left || right<uleft) return;
    
    if(uleft<=left && right<=uright) { 
        lazy[node]=diff;
        propagation(left,right,node);
        return;
    }
    int mid = (left+right)/2;
    update(left,mid,node*2,uleft,uright,diff);
    update(mid+1,right,node*2+1,uleft,uright,diff);
    tree[node]= tree[node*2]+tree[node*2+1];
}
 

 

이 코드에서 update 함수는 6개의 파라미터를 받는다. 현재 node가 가리키는 구간인 left와 right가 세 번째까지의 파라미터이고, uleft와 uright는 update를 수행할 구간을 나타내는 파라미터이다. long long int형의 diff는 update 해 줄 값을 의미한다.

 

만약 update를 요청하는 쿼리가 들어오면, 그 구간에 이전에 갱신해놓은 lazy값이 있는지 확인한다. 있다면 전파한다.(line 13)

 

그리고 구간을 확인하는데, 구간이 들어맞지 않으면 return하고, 구간이 정확히 맞다면 lazy값을 갱신한 후 propagate해 준다. propagate해 줄때 child node들의 lazy값에도 같은 값이 더해진다.(line 5-6)

 

구간이 걸쳐 있다면 recursive call을 하여 범위를 분할하여 update를 수행한다.

 

query 함수를 살펴보자.

 

ll query(int left, int right, int node, int qleft, int qright) {
   if(lazy[node]!=0) propagation(left,right,node);
    if(qleft > right || qright < left) return 0;
    if(left>=qleft && right<=qright) return tree[node];
    int mid = (left+right)/2;
    return query(left,mid,node*2,qleft,qright)+query(mid+1,right,node*2+1,qleft,qright);
}

 

query 함수는 크게 다르지 않다. 다만 query를 실행하기 전에 lazy가 비어있지 않다면 lazy값을 반영해주는 부분만 추가되었다.(line 2)

 

 

 

 

• 예제 적용 (BOJ 10999)

 

예제와 함께 접근해보자.

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

10999번: 구간 합 구하기 2

이 문제에서는 구간의 길이 N의 upper bound가 100만이다. query의 종류는 두 개인데, 구간 합을 구하는 쿼리와 구간 갱신을 하는 쿼리이다. 구간 합을 구하는 쿼리는 단순히 해결되지만, 일반 segment tree를 쓸 경우 구간 갱신 쿼리는 O(NlogN)에 수행되므로 update 쿼리의 upper bound인 M가 10000인 것을 고려하면 전체 time complexity는 O(KlogN + MNlogN)이므로 1초 내에 답을 낼 수 없다. 따라서 이 문제는 segment tree with lazy propagation으로 접근해야 한다.

 

다음과 같은 예제 입력이 들어온 상황을 보자.

5 2 2
1 2 3 4 5
1 3 4 6
2 2 5
1 1 3 -2
2 2 5

 

맨 처음에 tree는 다음과 같이 초기화된다 :

구간	1-5	1-3	4-5	1-2	3-3	4-4	5-5	1-1	2-2
index	1	2	3	4	5	6	7	8	9
value	15	6	9	3	3	4	5	1	2

 

query 1

처음 query인 1 3 4 6은 [3, 4]에 6을 더해주는 update를 수행하면 된다.

위 update함수에 의해서 node가 5일 때와 node가 6일 때 propagation이 수행되고, tree의 값은 다음과 같이 변경된다.

 

구간	1-5	1-3	4-5	1-2	3-3	4-4	5-5	1-1	2-2
index	1	2	3	4	5	6	7	8	9
value	27	12	15	3	9	10	5	1	2

root node의 값도 같이 변경된 것을 볼 수 있는데, line 25에 의해서 recursive call이 끝나고 난 후 tree[node] = tree[node*2] + tree[node*2+1]로 update되었기 때문이다.

 

query 2

두 번째 query는 2 2 5이다.

query는 필요한 구간에서 propagation을 실시하면 되고, 수행되는 node는 1, 2, 4, 8, 9, 5, 3 순서이다.

 

query 3

세 번째 query는 1 1 3 -2로, 구간 [1, 3]에 대해 2를 더해주어야 한다. propagate는 node 2에 대해서만 수행되고 node 2의 child node인 node 4와 node 5의 lazy값은 -2가 더해진다. 따라서 다음과 같은 상태가 된다.

구간	1-5	1-3	4-5	1-2	3-3	4-4	5-5	1-1	2-2
index	1	2	3	4	5	6	7	8	9
value	21	6	15	3	9	10	5	1	2

 

lazy의 상태는 다음과 같다.

구간	1-5	1-3	4-5	1-2	3-3	4-4	5-5	1-1	2-2
index	1	2	3	4	5	6	7	8	9
value	0	0	0	-2	-2	0	0	0	0

 

query 4

query 4는 summation이고, propagation은 1, 2, 4, 8, 9, 5, 3 순서로 진행된다. 이 때 tree의 state는 다음과 같이 변화된다.

구간	1-5	1-3	4-5	1-2	3-3	4-4	5-5	1-1	2-2
index	1	2	3	4	5	6	7	8	9
value	21	6	15	-1	7	10	5	-1	0

 

 

 

 

 

 

• references

https://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/

Lazy Propagation in Segment Tree - GeeksforGeeks