조금은 특별한 구간합 문제
앞선 세그먼트 트리에서는 숫자가 하나씩 바뀔 때마다 구간합을 구하는 문제를 해결하였습니다. 그런데 다음 같은 경우는 어떻게 될까요?
구간
[b, c]에서diff만큼 바뀐다.
최악의 경우를 생각해보면 시간복잡도는 O(NlogN) 씩 잡아먹는데, 이는 단순 누적합의 시간복잡도 O(N) 보다도 나쁩니다. 이를 해결하는 방식이 바로 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)입니다.
Lazy? Propagation?
그러면 Lazy는 뭐고 Propagation은 뭐고 Segment Tree with Lazy Propagation은 뭘까요? 각각을 정리하면 다음과 같습니다.
- Lazy : (게으르게) 여기 이거 갱신해야돼요 하고 표시만 하고 미루자!
- Propagation : 기본적으로 트리다보니... 부모에서 미룬거 처리 했으면 자식에게도 어 우리도 갱신해야돼요! 하고 표시해주자
- 이걸 세그먼트 트리에 적용해보자!
?? 아직도 뭔가 감이 안잡힙니다. 우선 구간합을 갱신하는 세그먼트 트리는 그대로 두되, 뭔가를 메모해두는 아이디어를 먼저 생각합니다. 이 메모하는 기존의 트리와 같은 배열을 lazy 라 두겠습니다.
그리고 갱신(update) 시에 구간으로 되어 있는 부분이 있으면, 해당 구간 발견시 더 갱신하지 말고 그냥 lazy[node]에 해당 값을 그냥 메모만 해놓는 것입니다! 그러면 구지 구간 전체를 일일히 갱신할 필요가 없습니다. 그러면 단순 세그먼트 트리와 동일한 시간복잡도를 가지게 됩니다.
그럼
lazy에 있는건 언제 갱신하나요?
갱신은 다른 update 또는 get을 할 때마다 추가적으로 lazy[node] 에 있는 것을 tree[node]로 계산을 반영 하는 메소드 updateLazy() 를 실행하는 것입니다. 그러면 뭔가 메소드 호출이 되는 동시에 알아서 잘 갱신이 됩니다.
작동 과정은 이 링크에 자세히 나와있습니다만, 사실 작동 과정을 직접 보는 것보다 lazy에 저장한다는 컨셉을 잘 이해하는게 실제 구현에는 도움이 되는 것 같습니다.
구현(달라진 점만)
updateLazy
lazy 배열을 tree로 옮기는 작업인데, 결국 lazy Propagation 이므로 부모에서 lazy 처리가 완료되면 부모는 비워주고 그 값을 자식에도 적용해야 되므로 자식에게 부모에서 처리한 것을 물려줍니다.
void updateLazy(long[] tree, long[] lazy, int node, int start, int end) {
if(lazy[node] == 0) return; // 저장된게 없으면 그대로 종료
tree[node] += (end - start + 1) * lazy[node]; // [start, end] 구간이므로 해당 구간 길이만큼 곱해준 값을 더해준다.
if(start != end) { // 자식이 있을 경우 Propagation 가능
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
}
lazy[node] = 0; // 끝나면 부모는 비우기
}get & updateTree
get
정말 딱 한줄만 추가됩니다. 바로 lazy에 있는 것을 tree에 반영만 하면 됩니다.
long get(long[] tree, long[] lazy, int node, int start, int end, int left, int right) {
updateLazy(tree, lazy, node, start, end); // lazy -> tree
if(right < start || end < left) return 0;
if(left <= start && end <= right) return tree[node];
int mid = (start + end) / 2;
long lsum = get(tree, lazy, 2 * node, start, mid, left, right);
long rsum = get(tree, lazy, 2 * node + 1, mid + 1, end, left, right);
return lsum + rsum;
}updateTree
get과 마찬자리로 lazy에 있는 것을 갱신하는 작업도 필요합니다. 하지만 여기서는 시간복잡도를 줄이는 핵심, 원하는 구간이 나오면 바로 lazy에 저장하는 테크닉이 필요합니다. 사실 그렇게 어렵진 않습니다. 바뀌는 부분만 주석으로 달면 아래와 같습니다.
void updateTree(long[] tree, long[] lazy, int node, int start, int end, int left, int right, int diff) {
updateLazy(tree, lazy, node, start, end); // lazy -> tree
if(right < start || end < left) return;
if(left <= start && end <= right) { // 원하는 구간 도착
tree[node] += (end - start + 1) * diff; // 역시 구간 길이를 고려한 구간 합 구하기
if(start != end) { // 더 나눌수 있는 경우(자식이 있는 경우)
lazy[2 * node] += diff; // updateLazy 때 처럼 자식에게 위임하자
lazy[2 * node + 1] += diff;
}
}
int mid = (start + end) / 2;
updateTree(tree, 2 * node, start, mid, index, diff);
updateTree(tree, 2 * node + 1, mid + 1, end, index, diff);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}출처
