반응형

Segment Tree with Lazy Propagation


Lazy Propagation란?


이전까지 알아온 Segment Tree는 하나의 값에 대해 update를 해주는 방식을 보곤했다.


하지만 구간 update는 이전 게시물에서는 존재하지 않았다.


이러한 구간 update를 일반 Segment Tree 소스 코드로 해결한다 생각해보자.


update는 시간 복잡도가 lgN이 든다.


그렇다면 a~b 구간을 update 하는데는 (b-a+1)*lgN이라는 시간 복잡도가 드는 것을 확인 할 수 있다.


이렇게 되면 상당한 크기의 Segment Tree를 수시로 업데이트 할 시 시간이 매우 오래 걸릴 수 있다.


따라서 이러한 TLE를 방지하고자 나타난 방식이 Lazy Propagation이다.


미리 말해두자면 이 Lazy Propagation의 시간 복잡도는 (lgN)^2이 걸린다.




Lazy Propagation 동작 과정


이 과정은 https://www.acmicpc.net/blog/view/26에


매우 설명이 잘 되어있으므로 다음 사이트에서 과정을 보시는 것을 추천합니다.








Lazy Propagation 소스 코드 및 설명


[10999번] 구간 합 구하기 2 :: https://www.acmicpc.net/problem/10999 


위 문제의 소스 코드를 통해 설명하겠습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
ll init(vector<ll> &arr, vector<ll> &tree, int node, int start, int end)
{
    if (start == end)
        return tree[node] = arr[start];
 
    int mid = (start + end) / 2;
 
    return tree[node] = init(arr, tree, node * 2, start, mid) + init(arr, tree, node * 2 + 1, mid + 1, end);
}
 
void update_lazy(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end)
{
    // lazy가 0이면 return;
    if (lazy[node] == 0)
        return;
    
    // 자식 노드가 있는 수 만큼 lazy값에 곱하여 더한다.
    // 자식에게 lazy를 분배하니 자식이 return으로 더해주지 못한 값을 직접 더한다.
    tree[node] += (end - start + 1) * lazy[node];
 
    // leaf가 아니면
    // 자식에게 lazy를 물려준다.
    if (start != end)
    {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
 
    // 물려준 후 lazy는 초기화
    lazy[node] = 0;
    
}
 
void update_range(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end, int left, int right, ll val)
{
    /*
        순서 ::
        1. lazy가 존재하면 업데이트 해준다.(tree[node] 변화)
        2. val을 더해준다.(자식수가 있는 만큼)
        2에서 자식 수만큼 더해주는 이유는 자식들은 아직 lazy가 업데이트 되지 않았기 때문
    */
    // 현재 노드에 lazy가 있는지 확인 후, lazy가 있다면 node를 업데이트 해준다.
    update_lazy(tree, lazy, node, start, end);
 
    // 하나도 속하지 않는다면 return;
    if (left > end || right < start)
        return;
 
    // 원하는 구간 내에 있는 노드에 왔을 경우
    if (left <= start && end <= right)
    {
        // 자식 노드가 있는 수 만큼 val을 곱해서 더해준다.
        // 자식이 return으로 더해주는 형태가 아니니 직접 더한다.
        tree[node] += (end - start + 1) * val;
 
        if (start != end)
        {
            lazy[node * 2] += val;
            lazy[node * 2 + 1] += val;
        }
        return;
    }
 
    int mid = (start + end) / 2;
    update_range(tree, lazy, node * 2, start, mid, left, right, val);
    update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right, val);
 
    // 구간이 걸쳐서 속해 있다면 자식 노드를 이용하여 부모 노드를 업데이트 한다.
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
 
ll sum(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end, int left, int right)
{
    // update이후 남은 lazy를 해당하는 구간을 sum 할 때 업데이트 해준다.
    update_lazy(tree, lazy, node, start, end);
 
    if (left > end || right < start)
        return 0;
 
    if (left <= start && end <= right)
        return tree[node];
 
    int mid = (start + end) / 2;
    return sum(tree, lazy, node * 2, start, mid, left, right) + sum(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int main()
{
    int n, m, k;
 
    scanf("%d %d %d", &n, &m, &k);
 
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (1 + h));
 
    vector<ll> arr(n);
    vector<ll> tree(tree_size);
    vector<ll> lazy(tree_size);
 
    for (int i = 0; i < n; i++)
        scanf("%lld", &arr[i]);
 
    init(arr, tree, 1, 0, n - 1);
    m += k;
 
    while (m--)
    {
        int num;
        scanf("%d", &num);
 
        if (num == 1)
        {
            int left, right;
            ll val;
 
            scanf("%d %d %lld", &left, &right, &val);
 
            update_range(tree, lazy, 1, 0, n - 1, left-1, right-1, val);
        }
 
        else if (num == 2)
        {
            int left, right;
            scanf("%d %d", &left, &right);
 
            printf("%lld\n",sum(tree, lazy, 1, 0, n - 1, left-1, right-1));
        }
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




void update_lazy(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end)


void update_lazy(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end)
{
    // lazy가 0이면 return;
    if (lazy[node] == 0)
        return;
    
    // 자식 노드가 있는 수 만큼 lazy값에 곱하여 더한다.
    // 자식에게 lazy를 분배하니 자식이 return으로 더해주지 못한 값을 직접 더한다.
    tree[node] += (end - start + 1) * lazy[node];
 
    // leaf가 아니면
    // 자식에게 lazy를 물려준다.
    if (start != end)
    {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
 
    // 물려준 후 lazy는 초기화
    lazy[node] = 0;
    
}


이 코드는 다음과 같다.


    // lazy가 0이면 return;
    if (lazy[node] == 0)
        return;
    


일단 lazy가 0이면 볼 필요없이 return;을 해주면 된다.


    // 자식 노드가 있는 수 만큼 lazy값에 곱하여 더한다.
    // 자식에게 lazy를 분배하니 자식이 return으로 더해주지 못한 값을 직접 더한다.
    tree[node] += (end - start + 1) * lazy[node];


그리고 tree[node] += (end - start + 1) * lazy[node];에서 


end - start + 1을 해주는 이유는 지금 이 코드는 lazy를 없애고 노드를 업데이트 시키는 상황이다.


따라서 원래는 lazy 없이 아래 자식노드에서 부모노드로 값을 return해주며 부모노드가 업데이트 되거나,


이전에 본 게시물들은 하나의 값만 업데이트 하는 것이기에 부모 노드에 업데이트 할 값(int diff = val - arr[pos-1]라고 쓰곤 함)을 더해주기만 하면 됐다.


하지만 지금은 lazy라는 값이 존재하고 자식에서 return도 못해주는 상황이고, 부모는 자식에게 lazy를 물려줘야하는 상황이니


결국 자식의 개수만큼 부모가 직접 노드를 update해야 한다.


    // 물려준 후 lazy는 초기화
    lazy[node] = 0;


마지막으로는 lazy를 0으로 초기화 해주면 된다.




void update_range(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end, int left, int right, ll val)


void update_range(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end, int left, int right, ll val)
{
    /*
        순서 ::
        1. lazy가 존재하면 업데이트 해준다.(tree[node] 변화)
        2. val을 더해준다.(자식수가 있는 만큼)
        2에서 자식 수만큼 더해주는 이유는 자식들은 아직 lazy가 업데이트 되지 않았기 때문
    */
    // 현재 노드에 lazy가 있는지 확인 후, lazy가 있다면 node를 업데이트 해준다.
    update_lazy(tree, lazy, node, start, end);
 
    // 하나도 속하지 않는다면 return;
    if (left > end || right < start)
        return;
 
    // 원하는 구간 내에 있는 노드에 왔을 경우
    if (left <= start && end <= right)
    {
        // 자식 노드가 있는 수 만큼 val을 곱해서 더해준다.
        // 자식이 return으로 더해주는 형태가 아니니 직접 더한다.
        tree[node] += (end - start + 1) * val;
 
        if (start != end)
        {
            lazy[node * 2] += val;
            lazy[node * 2 + 1] += val;
        }
        return;
    }
 
    int mid = (start + end) / 2;
    update_range(tree, lazy, node * 2, start, mid, left, right, val);
    update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right, val);
 
    // 구간이 걸쳐서 속해 있다면 자식 노드를 이용하여 부모 노드를 업데이트 한다.
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}



    /*
        순서 ::
        1. lazy가 존재하면 업데이트 해준다.(tree[node] 변화)
        2. val을 더해준다.(자식수가 있는 만큼)
        2에서 자식 수만큼 더해주는 이유는 자식들은 아직 lazy가 업데이트 되지 않았기 때문
    */
    // 현재 노드에 lazy가 있는지 확인 후, lazy가 있다면 node를 업데이트 해준다.
    update_lazy(tree, lazy, node, start, end);


처음에는 update_lazy를 통해 구간을 업데이트 하기 전, lazy가 존재하는지 확인한 후 lazy를 갱신해주어야 한다.



 
    // 원하는 구간 내에 있는 노드에 왔을 경우
    if (left <= start && end <= right)
    {
        // 자식 노드가 있는 수 만큼 val을 곱해서 더해준다.
        // 자식이 return으로 더해주는 형태가 아니니 직접 더한다.
        tree[node] += (end - start + 1) * val;
 
        if (start != end)
        {
            lazy[node * 2] += val;
            lazy[node * 2 + 1] += val;
        }
        return;
    } 


lazy는 lazy대로 처음에 update해주고 지금은 lazy에 관한 tree[node]에 더해주는 값이 아닌 실제 변경하고자 하는 값을 update해주는 것이다.


       // 자식 노드가 있는 수 만큼 val을 곱해서 더해준다.
        // 자식이 return으로 더해주는 형태가 아니니 직접 더한다.
        tree[node] += (end - start + 1) * val; 


tree[node]또한 자식에게 return 받지 않으니 자식의 수 만큼 직접 더하는 형태로 (end - start + 1) * val;로 구현해준다.


        if (start != end)
        {
            lazy[node * 2] += val;
            lazy[node * 2 + 1] += val;
        }


리프 노드가 아니라면 val만큼 자식 노드에 lazy를 추가해준다.




    // 구간이 걸쳐서 속해 있다면 자식 노드를 이용하여 부모 노드를 업데이트 한다.
    tree[node] = tree[node * 2] + tree[node * 2 + 1];



원래 Segment Tree의 update 코드대로라면 tree[node] += diff;라고 되어있지만 지금 범위 update 방식에서는


0~5의 배열로 구성된 Segment Tree에서


2~4의 구간을 업데이트 하고자 한다면 



　　　　　0~5


　　0~2　　　　　3~5


0~1　　2　　　3~4　　5


일 때 0~2는 2~4 구간 업데이트 부분에 걸쳐져 있기 때문에 따로 생각해주어야 한다.


따라서 위와 같이     tree[node] = tree[node * 2] + tree[node * 2 + 1]; 처럼 node를 갱신해주어야 한다.







ll sum(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end, int left, int right)


ll sum(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end, int left, int right)
{
    // update이후 남은 lazy를 해당하는 구간을 sum 할 때 업데이트 해준다.
    update_lazy(tree, lazy, node, start, end);
 
    if (left > end || right < start)
        return 0;
 
    if (left <= start && end <= right)
        return tree[node];
 
    int mid = (start + end) / 2;
    return sum(tree, lazy, node * 2, start, mid, left, right) + sum(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}




   // update이후 남은 lazy를 해당하는 구간을 sum 할 때 업데이트 해준다.
    update_lazy(tree, lazy, node, start, end);



update만 주구장창 하게 되면 update_range에 의해 남은 lazy가 생길 수 있다.


따라서 sum을 할 때 lazy가 존재하는지 최종적으로 체크 한 후 일반적인 세그트리 합과 같은 방식으로 구현하면 된다.


반응형
저작자표시 비영리 변경금지

'Applied > 자료구조' 카테고리의 다른 글

유니온 파인드(Union Find, Disjoint Set)  (16) 2017.03.23
펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)  (7) 2017.03.15
세그먼트 트리(Segment Tree)  (35) 2017.03.08
배열을 이용한 이진 탐색 트리(Binary Search Tree) 소스 코드  (0) 2017.03.02
맵(Map) STL 사용 방법  (0) 2017.02.20

티스토리툴바