> 레이지 프로퍼게이션(Lazy Propagation)
이번에도 트리에 관한 내용인데, 아마 다음엔 기하 관련 내용을 쓰지 않을까 싶습니다.
특히나 세그먼트 트리에 관한 내용입니다.
지금까지는 세그먼트 트리에는 2개의 연산이 있었습니다. 특정 인덱스의 값을 바꾸는 것과, 특정 구간의 합, 최댓값 등을 구하는 것.
그런데 레이지 프로퍼게이션(lazy propagation)이란 것을 사용하면 이런 연산도 가능합니다.
특정 구간 [a, b]에 값 c를 동시에 더한다
더한다는 연산은 다른 연산이 될 수도 있습니다. 보통은 구간합 트리가 많이 쓰이므로 더하는 연산이 됩니다.
저 연산을 naive하게 구현한다면 구간 [a, b] 안의 모든 인덱스에 c씩을 더하는 업데이트 연산을 할 것이므로 구간 길이가 K면 O(KlogN)의 시간이 드는데, K가 최대 N이니까 이 시간은 너무 클 수 있습니다.
레이지 프로퍼게이션을 사용한다면 이 연산 또한 단 O(logN)만에 가능합니다.
- BOJ[10999] : 구간 합 구하기 2
https://www.acmicpc.net/problem/10999
[
10999번: 구간 합 구하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄��
](https://www.acmicpc.net/problem/10999)
이 문제에서 요구하는 연산이 이렇습니다...
이 문제의 예제의 초기 세그먼트 트리를 그림으로 나타내면 아래와 같습니다.
맨 아래의 리프 노드 5개가 실질적인 값입니다. 오른쪽의 빈 3개 리프 노드와 그 부모들은 그냥 생략했습니다.
구간 합을 구하는 것이야 그냥 원래 세그먼트 트리에서 하던 대로 하면 되는데,
그럼 이제 구간에다 일정한 값을 더하는 연산을 어떻게 구현할 것이냐...!!
기존의 각 노드에 대응하는 구간 합 배열에 추가로 노드마다 값이 존재하는 lazy 배열을 만듭니다.
lazy 배열이 의미하는 바는, 이 노드의 영역 전체에 얼마만큼의 값을 더할 계획이 있다는 겁니다. 그러나 게을러서 아직 하지는 않았다... 언젠가는... 할 것이다... 이런 뜻입니다.
예를 들어, 맨 첫 번째 연산인 "1 3 4 6"을 시행하면 이와 같게 됩니다.
일단 구간 [3, 4]는 3, 4번 노드에 6을 더하라는 의미이므로...
해당 노드의 lazy 값이 6이 됩니다. 이건 이 노드 하의 값들에는 6을 더할 것이라는 의미입니다.
그러므로 훗날 만약 3번째나 4번째 인덱스를 포함한 구간의 합을 구해야 한다면, 6을 더한 결과를 알려줘야 한다는 겁니다.
물론 세상이 끝날 때까지 lazy 값을 저대로 방치할 수는 없고, 저 노드를 다시 만나게 되면 그제서야 자신의 자식 노드들로 lazy를 미룹니다. 이 과정이 propagation이 되겠습니다.
이렇게 계속 미루고, 미루다가 리프 노드에까지 lazy가 도달하게 되면, 리프 노드는 더 이상 미룰 자식이 없으므로 그냥 자신의 값에 lazy를 흡수합니다.
두 번째 연산 "2 2 5"를 시행하면, 저 [3, 4] 노드도 마주쳐야만 하므로 프로퍼게이션이 이루어집니다.
일단 나머지 인덱스 2, 5인 노드들이야 그냥 평소처럼 도달해서 값을 넘겨줄 것이고, 문제는 구간 [3, 4]인데요.
[3, 4] 노드가 자식들에게 lazy를 미루고, 자신은 6을 그만큼 더한 셈 치고 값에 12를 더합니다.
이 12는 자신이 포함하는 인덱스 개수인 2 * lazy 값 6입니다.
아직 리프 노드에 값이 더해진 건 아니지만 어쨌거나 언젠간 더할 것이고, 또 더한 것처럼 취급할 것이므로
앞으로 저 구간 노드를 만나면 더한 만큼의 값을 돌려주겠다는 겁니다.
결과적으로 쿼리의 답은 2+19+5=26이 됩니다.
그 다음 연산 "1 1 3 -2"를 가하면, 구간 [1, 3]은 노드 [1, 2]와 리프 노드 3으로 쪼개져 도달할 겁니다.
일단 [1, 2] 노드에는 아까처럼 lazy 값 -2가 생깁니다.
그리고 리프 노드 3은 도달했을 때 원래 lazy 값 6이 있었고, 자신이 리프니까 그냥 자기 값에 6을 더하고 나서 새로운 lazy 값 -2를 부여합니다.
그러나 여기서 끝이 아닙니다.
일단 자기 자신이 리프면 lazy 값을 자기한테 매기는 수고를 하지 말고, 걍 자기 자신한테 그 값을 더해버리는 게 낭비가 없을 겁니다.
따라서 자신에게 lazy 값 -2를 부여하지 말고 그냥 자기 값에 -2를 더합시다.
게다가 지금 그림도 뭔가 이상합니다.
3번 노드에는 7, 4번 노드에는 실질적으로 4+6=10이 있는데 그 부모 노드는 합 17이 아닌 19를 담고 있네요.
이건 그 자식 중 하나에 -2 값이 빼졌는데도 그걸 갱신하지 않은 결과입니다.
따라서 자식들의 프로퍼게이션이 모두 이루어진 후, 자신의 값도 자식들의 값을 사용해 갱신해 주도록 합시다.
최종 결과는 이렇게 됩니다.
4번 노드까지 lazy 값이 흡수된 게 뜬금없어 보일 수 있지만,
구간에 포함되건 안 되건 [3, 4] 노드가 자식 둘을 무조건 일단 호출은 하는 형태였으니까
호출을 하면 일단 자신의 lazy 값을 처리하게 되면서 이렇게 4번 노드도 처리가 된 것.
마지막 연산 "2 2 5"를 시행하면 인덱스 5야 아무것도 없으니까 제끼고, 리프 노드 2, 구간 노드 [3, 4]를 신경쓰면 될 것인데
구간 노드 [3, 4]야 보시는 대로 17이고, 리프 노드 5는 5, 남은 건 리프 노드 2인데...
리프 노드 2를 보기 위해 구간 노드 [1, 2]를 건드리면 거기 있던 lazy 값 때문에 프로퍼게이션이 일어나고, 결국 이렇게 됩니다.
그 결과, 쿼리의 답은 0+17+5=22가 됩니다.
#include <cstdio>
#include <algorithm>
using namespace std;
const int ST_MAX = 1<<21;
// 세그먼트 트리 구조체
struct SegTree{
int start;
long long arr[ST_MAX], lazy[ST_MAX];
// 생성자
SegTree(){
start = ST_MAX/2;
fill(arr, arr+ST_MAX, 0);
fill(lazy, lazy+ST_MAX, 0);
}
// 리프 노드들의 값을 먼저 입력한 후 전체 세그먼트 트리 구축
void construct(){
for(int i=start-1; i>0; i--)
arr[i] = arr[i*2] + arr[i*2+1];
}
// 구간 [ns, ne)인 node의 lazy 값을 propagate
void propagate(int node, int ns, int ne){
// lazy 값이 존재하면 실행
if(lazy[node] != 0){
// 리프 노드가 아니면 자식들에게 lazy 미룸
if(node < start){
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
// 자신에 해당하는 만큼의 값을 더함
arr[node] += lazy[node] * (ne-ns);
lazy[node] = 0;
}
}
// 구간 [s, e)에 k를 더하라
void add(int s, int e, int k){ add(s, e, k, 1, 0, start); }
void add(int s, int e, int k, int node, int ns, int ne){
// 일단 propagate
propagate(node, ns, ne);
if(e <= ns || ne <= s) return;
if(s <= ns && ne <= e){
// 이 노드가 구간에 완전히 포함되면 lazy 부여 후 propagate
lazy[node] += k;
propagate(node, ns, ne);
return;
}
int mid = (ns+ne)/2;
add(s, e, k, node*2, ns, mid);
add(s, e, k, node*2+1, mid, ne);
// 마지막에 자식들의 값을 사용해 다시 자신의 값 갱신
arr[node] = arr[node*2] + arr[node*2+1];
}
// 구간 [s, e)의 합을 구하라
long long sum(int s, int e){ return sum(s, e, 1, 0, start); }
long long sum(int s, int e, int node, int ns, int ne){
// 일단 propagate
propagate(node, ns, ne);
if(e <= ns || ne <= s) return 0;
if(s <= ns && ne <= e) return arr[node];
int mid = (ns+ne)/2;
return sum(s, e, node*2, ns, mid) + sum(s, e, node*2+1, mid, ne);
}
};
int main(){
// 초기 세그먼트 트리 입력받기
int N, M, K;
scanf("%d %d %d", &N, &M, &K);
SegTree ST;
for(int i=0; i<N; i++)
scanf("%lld", ST.arr+ST.start+i);
ST.construct();
// 쿼리 처리
for(int i=0; i<M+K; i++){
int a, b, c, d;
scanf("%d", &a);
if(a == 1){
scanf("%d %d %d", &b, &c, &d);
ST.add(b-1, c, d);
}
else{
scanf("%d %d", &b, &c);
printf("%lld\n", ST.sum(b-1, c));
}
}
}소스 코드입니다. propagate() 함수 부분을 주목하시면 됩니다.
또한 업데이트 함수도 구간을 받도록 바뀌었기 때문에, 구간 합 함수와 굉장히 구조가 비슷한 재귀 함수가 되었는데요.
이때 본인의 구간이 쿼리 구간에 완전 포함되면 lazy를 대신 매깁니다. 이때 바로 propagate를 해줘도 좋습니다.
또한 자신에서 함수가 종료되지 않았을 경우 마지막에 자식 노드들의 값을 통해 자신의 값을 갱신하는 것도 잊어서는 안 됩니다.
레이지 프로퍼게이션이 필요한 문제는 세그먼트 트리가 필요로 하는 연산이 무엇이냐에 따라 프로퍼게이션에서 처리해줘야 하는 일이 좀 달라지기 때문에 감이 잘 안 잡힐 수 있습니다.
물론 그냥 세그먼트 트리에 비해 등장빈도도 굉장히 적어도 연습하기도 힘든 건 덤. 응용문제를 풀어봅시다.
- BOJ[12844] : XOR
https://www.acmicpc.net/problem/12844
[
12844번: XOR
크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다.
](https://www.acmicpc.net/problem/12844)
일단 이 문제는 연산이 합에서 XOR로 바뀌었습니다. 프로퍼게이션을 구현하려면 연산의 성질을 잘 이해해야 합니다.
일단 뭐 모든 연산을 합에서 XOR 연산으로 바꾸면 되긴 하는데, 문제는
//자신에 해당하는 만큼의 값을 더함
arr[node] += lazy[node] * (ne-ns);구간 합 트리에서의 이부분. 이 부분 어떻게 될까요?
답은 ... 이 줄이 사라집니다! 정확히는 리프 노드가 아니라면 이 줄을 지워도 됩니다.
void(propagate(int node, int ns, int ne)){
if(lazy[node]!=0){
if(node < start){
lazy[node*2] ^= lazy[node];
lazy[node*2+1] ^= lazy[node];
}
else arr[node] ^= lazy[node];
lazy[node] = 0;
}
}이렇게 되는데, 왜 리프 노드일 때만 자신의 값을 갱신할까요?
왜냐면, 리프 노드가 아니라면 자신이 포함하는 구간은 항상 짝수 칸이기 때문입니다.
똑같은 값을 짝수 번 XOR 하면 0이 되죠... 따라서 하나 안 하나 결과가 그대로가 됩니다.
아, 이 문제 굉장히 양아치니까 조심하세요. 구간 정보 a, b가 들어왔을 때 a>b일 수도 있습니다...
- BOJ[1395] 스위치
https://www.acmicpc.net/problem/1395
[
1395번: 스위치
첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O��
](https://www.acmicpc.net/problem/1395)
이 문제는 조금 더 어렵습니다. 일단 각 노드의 기본값은 이 구간 안에 켜져 있는 스위치 개수인 건 맞습니다.
문제는 lazy. 스위치는 항상 그 상태를 반전시킬 수만 있는데, 만약 하나의 스위치를 두 번 반전시키면 원래 상태가 되므로, lazy 값을 bool 타입으로 표현할 수 있습니다.
// 구간 [ns, ne)인 node를 propagate
void propagate(int node, int ns, int ne){
if(lazy[node]){
// 리프 노드가 아님
if(node < start){
lazy[node*2] ^= 1;
lazy[node*2+1] ^= 1;
// 왼쪽 자식과 오른쪽 자식의 결과로 자신의 결과 갱신
int temp = 0;
// 만약 왼쪽 자식 전체가 반전될 것이라면, 실질적인 값은 구간 크기 - 현재 값
if(lazy[node*2]) temp += (ne-ns)/2 - arr[node*2];
// 아니면 그냥 현재 값
else temp += arr[node*2];
// 오른쪽 자식도 마찬가지
if(lazy[node*2+1]) temp += (ne-ns)/2 - arr[node*2+1];
else temp += arr[node*2+1];
arr[node] = temp;
}
// 리프 노드
else arr[node] ^= 1;
lazy[node] = false;
}
}
// 구간 [s, e)의 상태를 반전시켜라
void turn(int s, int e, int node, int ns, int ne){
propagate(node, ns, ne);
if(e <= ns || ne <= s) return;
if(s <= ns && ne <= e){
// lazy 값을 반전시킴
lazy[node] ^= 1;
propagate(node, ns, ne);
return;
}
int mid = (ns+ne)/2;
turn(s, e, node*2, ns, mid);
turn(s, e, node*2+1, mid, ne);
arr[node] = arr[node*2] + arr[node*2+1];
}propagate() 함수에서 자신의 arr 값을 갱신하는 부분을 주목해야 합니다.
lazy 값은 true 또는 false입니다. true면 반전을 시킬 거란 말입니다. 홀수 번 반전시키는 건 다 true와 같고, 짝수 번 반전시키는 건 다 false와 같죠.
이때, 만약 자기 자식의 lazy 값이 true라면 그 자식 구간에 속한 켜져 있는 스위치 개수는 사실상 arr 값의 반대일 겁니다. 왜냐면 앞으로 꺼져 있던 게 켜질 것이고 켜져 있던 건 꺼질 것이니까.
레이지 관련 추천 문제
10999번: 구간 합 구하기 2
위에서 설명한 문제입니다.
12844번: XOR
위에서 설명한 문제입니다.
1395번: 스위치 (★)
위에서 설명한 문제입니다.
10713번: 기차 여행
각 도로마다 이 도로를 전체 여행 중 몇 번 지나치는지를 각각 세야 하는데, 이를 구간 갱신 쿼리로 구합니다.
마지막으로 각 도로마다, A, B, C 값을 받아서 지난 횟수와 조합해 보고 어느 쪽이 더 싼지 각각 판단해서 더하면 됩니다.
다른 풀이가 존재하는 문제입니다.
16404번: 주식회사 승범이네 (★)
사원들의 관계를 루트 노드가 정해진 트리로 나타내고, 위와 같이 서브트리가 반드시 연속된 수들로만 이루어지도록 전위 순회나 후위 순회로 각 사원에게 번호를 매길 수 있습니다.
그리고 번호를 매기면서 각 사원을 루트로 하는 서브트리에서 제일 작은 정점 번호와 제일 큰 정점 번호도 쉽게 구해 나갈 수 있습니다.
이렇게 각 사원에게 정점 번호를 부여한 후, 주어지는 질의를 이 정점 번호들에 대해서 하면 됩니다. 예를 들어 저기서 정점 번호가 6번인 사원에게 손익이 발생했다면 6~8 구간에 레이지 프로퍼게이션을 시행하는 식으로 풀 수 있습니다.
13925번: 수열과 쿼리 13 (★)
상당한 발상이 필요한 문제.
lazy 배열이 독특합니다. 기존에는 lazy[node] = k라면 node 휘하에 전부 k를 더할 것이라는 의미였는데, lazy 값으로 a, b 이렇게 2개를 관리해서 node 휘하의 모든 값을 a*(val) + b로 만들 것이라는 의미를 부여하면 문제를 풀 수 있습니다.
디폴트로는 a = 1, b = 0이면 되고, v를 더하는 연산은 b에 v를 더하고, v를 곱하는 연산은 a와 b에 v를 곱하고, v로 만드는 연산은 a = 0, b = v로 만드는 식으로 propagate하면 됩니다.
'알고리즘 > [ 개념 ]' 카테고리의 다른 글
| [ 개념 ] 48. 트라이(Trie).ver2 (2) | 2020.09.25 |
|---|---|
| [ 개념 ] 47. 스위핑 알고리즘(Sweeping Algorithm) (0) | 2020.09.22 |
| [ 개념 ] 45. 볼록 껍질(Convex Hull) (0) | 2020.09.22 |
| [ 개념 ] 44. 이분 매칭(Bipartite Matching) (2) | 2020.09.17 |
| [ 개념 ] 43. 네트워크 유량(Network Flow) (6) | 2020.09.16 |