[목차]
1. Lazy Propagation이란?
2. Lazy Propagation with Segment Tree
3. Lazy Propagation with Fenwick Tree
4. Lazy Propagation 예시 문제
1. Lazy Propagation이란?
혹시 세그먼트 트리(Segment Tree)와 펜윅 트리(Fenwick Tree)에 대해서 잘 모른다면 이 자료구조들에 대해서 학습한 후, 이 글을 보는 것을 권장한다.
세그먼트 트리나 펜윅 트리는 원소의 update가 있는 경우에 구간합을 빠르게 구해주기 위해서 사용한다.
한 원소의 update는 O(logN)만큼의 시간이 걸리고, 구간합 또한 O(logN)만큼의 시간이 걸리기 때문에
Q를 쿼리의 개수라고 하면 보통 O(QlogN) 만큼의 시간이 필요하다.
하지만, 만약 하나의 원소가 아니라, 원소가 여러 개인 '구간'을 update 한다면 어떨까?
기존의 세그먼트 트리나 펜윅 트리는 하나의 원소만 update 할 수 있으므로, 구간의 길이를 M이라고 하면
O(MlogN)의 update 시간이 걸리게 된다.
그러므로 최악의 경우 한번 update하는데만 O(NlogN)의 시간이 필요하므로 많은 쿼리가 들어오는 경우에는 이 방식을 사용하기 힘들다는 것을 쉽게 알 수 있다.
이 경우에 이용되는 것이 Lazy Propatation 기법이다. 말 그대로 번역하면 "게으른 전파" 이다.
예시를 통해서 한번 살펴보자.
이해하기 쉽게 쿼리를 가장 기본적인 '구간 합'이라고 가정하자.
원소가 10개인 배열을 세그트리에 저장하게 되면 위의 그림과 같이 나타난다.
각 노드에 적혀있는 구간은 노드가 담고 있는 구간이다.
예를 들어서 6 ~ 8 노드라고 한다면 A[6] + A[7] + A[8]의 값을 담고 있다.
이제 여기서 구간 [4, 7]을 update하는 경우를 생각해보자.
아래 그림에서 구간 [4, 7]을 update할 때 변경해야 하는 노드들은 하늘색 노드이다.
다음은 구간합을 구하는 경우를 생각해보자.
잘 생각해보면 update를 한 후에 4 ~ 5를 완전히 포함하는 구간, 예를 들어 [1, 7]과 같은 구간의 합을 구한다면
굳이 리프노드인 4와 5까지 내려갈 필요 없이 4 ~ 5 노드까지만 내려간 후 노드의 값을 return 해주면 된다.
만약 [1, 4] 구간의 합을 구하는 경우엔, 4 ~ 5 노드에서 return 하게 되면 5번 노드의 값도 더해지기 때문에 이 경우에는 4 노드까지 내려간 후에 return 해주어야 한다.
따라서 이를 통해서, 구간합을 구하는데 필요한 노드까지만 update를 하고 나머지 아래 노드들은 나중에 필요할 때 한번에 update해도 괜찮지 않을까?라는 아이디어를 얻을 수 있다.
여기서 Lazy Propagation, 게으른 전파라는 용어의 의미를 알 수 있다.
아래 그림은 [4, 7] 구간을 update하는 경우에 update 되는 노드를 초록색으로 표시한 그림이다.
원래는 10개의 노드를 update 해야하지만, 6개의 노드만 update해도 충분하다는 것을 알 수 있다.
Lazy Propagation 기법을 이용하면 구간 업데이트를 O(NlogN)이 아닌, O(logN)만에 수행할 수 있다.
즉, 점 업데이트와 동일한 시간 내에 수행이 가능한 엄청난 장점을 가지고 있다.
2. Lazy Propagation with Segment Tree
이제, Segment Tree로 Lazy Propagation을 구현하는 방법을 알아보자.
먼저, Lazy Propagation을 이용하기 위해서는 나중에 update 시켜줄 값을 저장하는 lazy 배열이 추가로 필요하다.
구간 업데이트(Range update)를 하는 코드는 아래와 같다.
void update_range(int x, int s, int e, int l, int r, int dx) {
update_lazy(x, s, e);
if (e < l || s > r) return;
if (s >= l && e <= r) {
tree[x] += (e - s + 1)*dx;
if (s != e) {
lazy[x << 1] += dx;
lazy[(x << 1) + 1] += dx;
}
return;
}
update_range(x << 1, s, (s + e) / 2, l, r, dx);
update_range((x << 1) + 1, (s + e) / 2 + 1, e, l, r, dx);
tree[x] = tree[x << 1] + tree[(x << 1) + 1];
}
update_lazy 함수는 미뤄뒀던 update를 수행하는 함수이다. 뒤에서 살펴보자.
먼저 현재 노드가 update하는 구간과 겹치지 않는다면 아무것도 수행하지 않고 종료한다.
현재 노드가 update하는 구간에 완전히 포함된다면 현재 노드를 update 해준다.
이때, 단순히 dx를 더해주는 것이 아니라, 현재 노드의 구간 길이만큼 곱해서 더해주는 것에 주의하자.
그리고 s != e인 경우, 즉 리프 노드가 아닌 경우에는 이후의 노드들의 update는 나중에 해주어야 하므로
자식 노드에만 우선 lazy배열에 값을 저장해둔다. (자식의 자손들은 update_lazy 함수를 통해 전달된다)
현재 노드가 update하는 구간에 포함되지 않으면서 겹친다면 구간을 둘로 나눠서 재귀 호출을 해주고,
자식 노드를 이용해서 현재 노드의 값을 업데이트해준다.
update_lazy 함수를 살펴보자.
void update_lazy(int x, int s, int e) {
if (lazy[x] != 0) {
tree[x] += (e - s + 1)*lazy[x];
if (s != e) { //no leaf
lazy[x << 1] += lazy[x];
lazy[(x << 1) + 1] += lazy[x];
}
lazy[x] = 0;
}
}
현재 노드에서 lazy값이 0이 아닌 경우, 즉 update할 값이 남아있는 경우에는 현재 노드를 update 해주고 자식 노드에 lazy값을 넘겨준다.
update_range 함수와 함께 연관지어서 보면 더 이해가 잘 될 것이다.
항상 lazy값은 현재 노드의 자식에만 넘겨주는 것을 참고하자.
구간합을 구하는 쿼리는 기존의 segment tree 코드와 차이가 없다.
다만, 합을 구하는 경우에 현재 노드를 update하는 코드인 update_lazy(x, s, e)만 추가되었다.
int sum(int x, int s, int e, int l, int r) {
update_lazy(x, s, e);
if (s > r || e < l) return 0;
if (s >= l && e <= r) return tr[x];
return sum(x * 2, s, (s + e) / 2, l, r) + sum(x * 2, (s + e) / 2 + 1, e, l, r);
}
www.acmicpc.net/blog/view/26 에 자세한 설명이 나와있다.
3. Lazy Propagation with Fenwick Tree
펜윅 트리는 세그먼트 트리보다 범용성은 낮지만, 이용할 수 있는 경우에는 세그먼트 트리보다 효율이 훨씬 뛰어나다.
코드 길이는 물론 메모리와 시간까지 세그먼트 트리에 비해 더 나은 성능을 보인다.
먼저 기존의 펜윅 트리 방식을 안다고 가정하고, 짧게만 언급하겠다.
혹시나 아직 펜윅 트리에 대해서 잘 모른다면 이 게시글을 참고하자. www.acmicpc.net/blog/view/21
우선 펜윅 트리에서의 구간 업데이트 & 점 쿼리 (Range update & point query)는 꽤나 간단하다.
B[i] = A[i] - A[i-1]을 만족하는 새로운 수열 B[i]를 생각해보자.
그러면 수열 A의 [L, R] 구간에 x만큼 더해준다고 하면, 수열 B에서는 B[L]에 x를 더하고, B[R+1]에 -x를 더하는 것과 동일하다.
A[L] ~ A[R] 까지의 차이는 변함없고, A[L-1]과 A[L], A[R]과 A[R+1]간의 차이만 달라지기 때문이다.
그다음에 하나의 원소 A[k]를 구하고 싶다면
A[k] = (A[k] - A[k-1]) + (A[k-1] - A[k-2]) + ... + (A[1] - A[0]) = B[k] + B[k-1] + ... + B[1] 을 만족하므로
결국 B의 [1, k] 구간합을 구해주면 된다.
요약하면 다음과 같다.
1. 수열 A의 구간 [L, R]에 각각 x를 더해준다 : update(L, x) & update(R+1, -x)
2. A[k]를 출력한다 : sum(k)
int sum(int i) {
int ans = 0;
while (i > 0) {
ans += tr[i];
i -= (i & -i);
}
return ans;
}
void update(int i, int val) {
while (i <= N) {
tr[i] += val;
i += (i&-i);
}
}
int main(void){
update(l, x);
update(r + 1, -x);
sum(k);
}
펜윅 트리에서의 구간 업데이트 & 구간 쿼리 (Range update & Range query)도 가능하다.
다만, 이 경우에는 펜윅 트리가 2개 필요하다.
다음의 두 쿼리를 생각해보자.
1. 구간 [k, N]의 원소에 각각 x를 더한다.
2. 구간 [1, k]의 원소의 합을 구한다.
쿼리 1을 수행했을 때, [k, N] 사이에 있는 i에 대해서 i번째까지 원소의 합은 $(i - k + 1)x$ 만큼 증가한다.
$f(i) = ix + (-k + 1)x$ 로 분리해서 생각해보면, 이 함수를 k번째 원소에 집어넣는 펜윅 트리라고 생각할 수 있다.
따라서 일차항의 계수 $x$와 상수항인 $(-k+1)x$를 각각 다른 펜윅 트리에 저장하고,
일차함수의 합은 그대로 일차함수이므로 [1, k] 구간의 합을 통해서 새로운 일차함수를 얻은 다음 k를 대입하면 쿼리 2의 값이 나온다.
따라서 쿼리 1과 쿼리 2를 통해서 구간 업데이트 & 구간 쿼리를 펜윅 트리로 구현할 수 있다.
아래 코드를 통해서 이해해보자.
int a_tr[100001]; //일차항 계수
int b_tr[100001]; //상수항
int sum(int tr[], int i) {
int ans = 0;
while (i > 0) {
ans += tr[i];
i -= (i & -i);
}
return ans;
}
void update(int tr[], int i, int val) {
while (i <= N) {
tr[i] += val;
i += (i&-i);
}
}
int main(void) {
//Range update [L, R]
update(a_tr, L, x); update(a_tr, R + 1, -x); //일차항 계수 update
update(b_tr, L, (-L + 1)*x); update(b_tr, R + 1, R*x); //상수항 update
//Range query [L, R]
int res = 0;
res += sum(a_tr, R)*R + sum(b_tr, R); //[1 , R]
res -= sum(a_tr, L - 1)*(L - 1) + sum(b_tr, L - 1); //[1, L-1]
}
4. Lazy Propagation 예제 문제
Lazy propagation을 이용하는 문제들이 많이 있다.
그중 어렵지 않으면서, 사람들이 많이 푼 기본 문제들을 몇 개 선별해보았다. (풀이를 보고 싶다면 더보기를 누르면 된다)
[백준 10999번] 구간 합 구하기 2
풀이)
lazy propagation을 이용하는 가장 기본적인 문제이다.
별다른 테크닉이나 아이디어가 필요 없다.
[백준 2934번] LRH 식물
풀이)
어려운 문제는 아니지만, 주의해야 할 사항이 몇 개 있다.
이미 꽃이 있는 경우에는 꽃이 피지 않기 때문에 새로 들어오는 식물의 L, R좌표인 부분은 0으로 update 시켜주어야 한다.
또 반드시 선분이 '교차'해야 꽃이 피는 점을 주의하자.
[백준 1395번] 스위치
풀이)
구간 합 구하기 2와 마찬가지로 기본적인 lazy propagation 문제이다.
스위치가 켜지거나 꺼지는 두 가지 경우밖에 없기 때문에 update를 할 때 xor을 이용할 수 있다.
[백준 16404번] 주식회사 승범이네
풀이)
오일러 경로 테크닉이라는 멋있는 이름의 태그가 붙어있지만 사실 엄청 어려운 개념이 아니다.
그래프를 dfs로 탐색할 때, 방문 순서를 노드 번호로 붙여준다.
그리고 현재 노드의 번호를 L이라고 하고, 자신을 루트로 하는 서브 트리에서 가장 번호가 큰 번호를 R이라고 하면
그 서브트리에 속한 노드들의 범위는 연속하는 구간 [L, R]을 만족하게 된다.
이후에 lazy propagation을 이용해주면 된다.
[백준 17353번] 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별
[백준 14288번] 내리 칭찬 4
풀이)
16404 문제와 유사하다.
다만 추가적인 문제로, 이번에는 자식에서 부모로 쭉 올라가는 경우도 있다.
이는, 세그 트리를 하나 더 만들어서 만약 상사 방향인 경우에는 현재 노드만 업데이트해주게 되면,
현재 노드를 자손으로 하는 모든 조상들이 업데이트가 된다.
[백준 20190번] 버블버블
PC로 보시는 것을 권장합니다.
피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^
'알고리즘' 카테고리의 다른 글
| 병렬 이분 탐색(Parallel Binary Search) (1) | 2021.08.02 |
|---|---|
| [자료구조] 트라이(Trie) 자료구조 (3) | 2020.12.13 |
| [DFS] 그래프 간선의 분류 / 사이클(Cycle) 찾기 (0) | 2020.11.10 |
| [분할 정복] L-트로미노(L-Tromino) 타일링 (0) | 2020.10.16 |
| 비트마스크 (BitMask) 알고리즘 (3) | 2020.10.15 |
