[자료구조] 백준 10999번: 구간 합 구하기 2 (C++), Lazy Propagation

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

10999번: 구간 합 구하기 2

앞선 세그먼트 트리 정리에서 구간 업데이트를 할 때는 Lazy Propagation을 통해 O(logN)으로 구현할 수 있다고 했다. 물론 구간합 함수를 참고하여 구간 업데이트를 할 수 있지만 이는 O(NlogN)으로 시간 초과가 난다.

 

Lazy Propagation에 대해서는 다음 블로그를 참고하여 공부했다.

(https://yabmoons.tistory.com/442)

엄청 디테일하게 설명해놓으셔서 빠르게 이해할 수 있었다.

 

[Lazy Propagation 정리]

아직 미숙해서 설명이 잘 안 되어있거나 이상한 부분이 있을 수 있다. 시간이 지나서 Lazy Propagation에 대해 다시 한번 정리할 기회가 있었으면 좋겠다. 참고한 블로그를 여러 번 보는 게 도움이 될 거 같다.

[용도]

구간 합을 구하는 쿼리를 통하여 구현할 수도 있지만 앞서 말한대로 O(NlogN)에서 O(logN)으로 줄이기 위해 사용한다.

>> 구간 업데이트를 위해 필요한 빠른 방법

[개요]

구간에 속한 일부 노드만 업데이트하고, 다음 업데이트에 영향을 미치지 않게끔만 미루고 미루다가 업데이트 함으로써 시간을 최대한 줄인다.

 

[구현]

[Lazy: 업데이트 해야할 값]

Lazy Propagation을 구현하기 위해서는 트리 형식의 배열 lazy가 필요하다. 트리 형식이므로 Segment Tree와 같은 사이즈의 배열이 필요하다.

 

Lazy에는 어떤 값을 담는가? index 3 ~ 8까지 +2를 하라고 했을 때

각 노드에 더해야 할 값들이 있다.

[0, 8] 노드

[0, 4] 노드

[3, 4] 노드

[3] 노드

[4] 노드

[5, 8] 노드

[5, 6] 노드

[5] 노드

[6] 노드

[7, 8] 노드

[7] 노드

[8] 노드

해당 노드에 (구간 길이) * (+2) 씩 더해줘야 한다.

그래서 Lazy에는 해당 노드에는 (+2)만큼 업데이트해야 한다고 알려줘야 하기 때문에 (+2)를 담는다.

>> 여기서 알 수 있는 건 Lazy의 값이 0이라면 업데이트 할 것이 없다. 0이 아니라면 업데이트 안 하고 미루고 있던 게 있다 라고 정리할 수 있다.

그럼 위에 적은 노드들의 모든 Lazy 값을 세그먼트 트리에 업데이트해줘야 할까?

>> 아니다. 업데이트에 불필요한 계산을 줄이려고 Lazy Propagation을 하기 때문에 개요와 어긋난다.

>> 각 노드의 Lazy 값은 놔두고, 업데이트가 필요한 노드들만 Lazy값을 써서 업데이트를 해주면 된다.

 

[lazyUpdate: 필요한 노드만 업데이트]

Lazy를 업데이트는 함수를 한 번 정리해보자.

lazy를 업데이트하는 함수는 두 가지 경우에서 쓰인다.

• 구간 업데이트를 할 때
• 구간 쿼리를 구할 때

두 가지 경우에서 쓰이는 이유는 구간 업데이트나 구간 쿼리를 구할 때

'지금 이 구간 노드 써야한다. 업데이트해야 할 거 다 해놓고 내놔라' 이런 식으로 받아들이면 된다.

 

위에서 말했듯이 lazy값이 0이라면 '업데이트 할 것이 없다.' 혹은 '이미 업데이트 다 되어있다.' 이런 뜻이다.

0이 아니라면 업데이트할 것이 있다는 뜻이고 lazy값에 구간 길이만큼 곱하고 Segment Tree에다가 업데이트를 해준다.

그리고, 업데이트 한 노드가 leaf노드가 아니었다면 자식 노드에게 lazy값을 물려줘야 한다.

물려주고 나서 업데이트를 했으므로 해당 lazy값은 0으로 바꿔준다.

 

>> 자식 노드에게 lazy 값을 물려주는 이유

업데이트는 한 번으로 끝나지 않는다. 다음 구간 합을 구할 때 [0, 3]부터 구한다고 치면

자식 노드에 물려주지 않았을 때는 3을 가리키는 leaf 노드에 업데이트할 lazy값이 없다고 나오기 때문에 오류가 나게 된다.

 

그리고, 상식적으로도 애초에 [3, 8]구간의 합을 구하는데 3에 업데이트할 게 없다고 되어있으면 말이 되지 않는다.

void lazyUpdate(int node, int start, int end) {
	if (lazy[node] != 0) { // 해당 노드를 사용해야 하는데
		// 업데이트 해야 할 lazy 값이 있다면?
		sgTree[node] = sgTree[node] + (end - start + 1) * lazy[node];
		if (start != end) { // 자식 노드가 있다면?
			// 자식 노드에게 lazy 값 물려주기
			lazy[node * 2] = lazy[node * 2] + lazy[node];
			lazy[node * 2 + 1] = lazy[node * 2 + 1] + lazy[node];
		}
		// 업데이트가 끝났으니 해당 노드의 lazy값 0
		// 이 부분은 자식 노드와 상관없으니 헷갈리지 말기
		lazy[node] = 0;
	}
}

 

[Update: 필요한 구간을 업데이트 하는 함수]

Update도 3가지 경우로 나뉜다. 노드가 가리키는 구간이

• 완전히 범위를 벗어난 경우
• 현재 노드가 담당하는 구간이 찾고자하는 구간에 완전히 속한 경우
• 구간이 걸쳐있는 경우

어쨌거나 이 3가지 경우에 들어가기 전에 해당 노드를 사용할 수 있으므로 lazyUpdate를 해준다.

 

1) 완전히 범위를 벗어난 경우

>> 필요없으므로 종료시킨다.

2) 현재 노드가 담당하는 구간이 찾고자 하는 구간에 완전히 속한 경우

>> 해당 노드까지만 업데이트해주고, 자식 노드에게 lazy 값을 물려주고 종료한다.

3) 구간이 걸쳐있는 경우

>> 더 나눠서 진행해야 한다.

void update(int node, int start, int end, int left, int right, ll value) {
	// 0) Lazy 값을 확인하고 해당 노드들 업데이트 하는 것이 가장 우선적
	lazyUpdate(node, start, end);

	// 1.1) 완전히 범위를 벗어난 경우
	if (right < start || left > end) return;

	// 1.2) 현재 노드가 담당하는 구간이 찾고자하는 구간에 완전히 속한 경우
	// >> 즉각적으로 업데이트 및 Lazy값 물려주기
	if (left <= start && end <= right) {
		// 현재 노드까지만 업데이트 시켜준다.
		sgTree[node] = sgTree[node] + (end - start + 1) * value;
		// 그 아래 자식 노드들은 업데이트 X, lazy값만 물려준다.
		if (start != end) {
			lazy[node * 2] = lazy[node * 2] + value;
			lazy[node * 2 + 1] = lazy[node * 2 + 1] + value;
		}
		return;
	}

	// 1.3) 구간이 걸쳐있는 경우
	// >> 더 나눠야 한다.
	int mid = (start + end) / 2;
	update(node * 2, start, mid, left, right, value);
	update(node * 2 + 1, mid + 1, end, left, right, value);
	sgTree[node] = sgTree[node * 2] + sgTree[node * 2 + 1];
}

[query: 쿼리 값을 반환하는 함수]

일반적인 쿼리처럼 작성하되 쿼리를 구하기 전에 lazyUpdate를 해줘야 한다. 아직 업데이트 안 된 노드들을 사용할 수도 있기 때문이다.

ll query(int node, int start, int end, int left, int right) {
	lazyUpdate(node, start, end);
	if (right < start || left > end) return 0;
	if (left <= start && end <= right) return sgTree[node];

	int mid = (start + end) / 2;
	return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right);
}

 

[AC 코드]

#include <iostream>
#define MAX (1000000 + 1)
#define ll long long
using namespace std;

ll arr[MAX];
ll sgTree[MAX * 4];
ll lazy[MAX * 4];
int n, m, k;

ll sgInit(int start, int end, int node) {
	if (start == end) {
		return sgTree[node] = arr[start];
	}
	int mid = (start + end) / 2;
	return sgTree[node] = sgInit(start, mid, node * 2) + sgInit(mid + 1, end, node * 2 + 1);
}

void lazyUpdate(int node, int start, int end) {
	if (lazy[node] != 0) { // 해당 노드를 사용해야 하는데
		// 업데이트 해야 할 lazy 값이 있다면?
		sgTree[node] = sgTree[node] + (end - start + 1) * lazy[node];
		if (start != end) { // 자식 노드가 있다면?
			// 자식 노드에게 lazy 값 물려주기
			lazy[node * 2] = lazy[node * 2] + lazy[node];
			lazy[node * 2 + 1] = lazy[node * 2 + 1] + lazy[node];
		}
		// 업데이트가 끝났으니 해당 노드의 lazy값 0
		// 이 부분은 자식 노드와 상관없으니 헷갈리지 말기
		lazy[node] = 0;
	}
}

void update(int node, int start, int end, int left, int right, ll value) {
	// 0) Lazy 값을 확인하고 해당 노드들 업데이트 하는 것이 가장 우선적
	lazyUpdate(node, start, end);

	// 1.1) 완전히 범위를 벗어난 경우
	if (right < start || left > end) return;

	// 1.2) 현재 노드가 담당하는 구간이 찾고자하는 구간에 완전히 속한 경우
	// >> 즉각적으로 업데이트 및 Lazy값 물려주기
	if (left <= start && end <= right) {
		// 현재 노드까지만 업데이트 시켜준다.
		sgTree[node] = sgTree[node] + (end - start + 1) * value;
		// 그 아래 자식 노드들은 업데이트 X, lazy값만 물려준다.
		if (start != end) {
			lazy[node * 2] = lazy[node * 2] + value;
			lazy[node * 2 + 1] = lazy[node * 2 + 1] + value;
		}
		return;
	}

	// 1.3) 구간이 걸쳐있는 경우
	// >> 더 나눠야 한다.
	int mid = (start + end) / 2;
	update(node * 2, start, mid, left, right, value);
	update(node * 2 + 1, mid + 1, end, left, right, value);
	sgTree[node] = sgTree[node * 2] + sgTree[node * 2 + 1];
}

ll query(int node, int start, int end, int left, int right) {
	lazyUpdate(node, start, end);
	if (right < start || left > end) return 0;
	if (left <= start && end <= right) return sgTree[node];

	int mid = (start + end) / 2;
	return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	sgInit(1, n, 1);

	for (int i = 0; i < m + k; i++) {
		int a;
		cin >> a;
		if (a == 1) {
			int b, c;
			ll d;
			cin >> b >> c >> d;
			update(1, 1, n, b, c, d);
		}
		else {
			int b, c;
			cin >> b >> c;
			cout << query(1, 1, n, b, c) << '\n';
		}
	}
	return 0;
}