BOJ 10999 : 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation)

알고리즘 문제 전체 링크

삼성 B형 전체 링크

삼성 C형 전체 링크

 

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

 

참고

- 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition)

- 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree)

- 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree)

- 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation)

 

 

BOJ 2042 - 구간 합 구하기와 비슷한 문제지만, 배열의 갱신이 연속된 특정 구간에 발생한다.

매 구간마다 하나씩 구간의 값을 바꾸면 느리기 때문에 알고리즘을 보완해야 한다.

 

느리게 갱신되는 세그먼트 트리를 이용해 문제를 풀어보자.

---

Top-Down Segment Tree

 

주어진 구간의 합을 구해야할 배열이 다음과 같다고 하자.

 

탑 다운 세그먼트 트리의 node에 아래의 구간의 합이 저장된다.

 

실제 저장된 값은 아래와 같다.

 

이제 구간 [1 ~ 6]의 원소를 모두 1씩 증가시킨다고 해보자.

모든 구간을 update하는 것은 비효율적이다.

 

구간 [1 ~ 6]은 구간 [1 ~ 4]와 구간 [5 ~ 6]으로 나눌 수 있다.

따라서 아래 표시된 구간만 업데이트하고 나머지는 나중에 필요할 때 update하면 된다.

여기서 필요할 때란, 해당 구간의 값을 정확히 알아야 할 때이다.

 

예를 들어서 이 상태에서 구간 [1 ~ 6]의 합을 구한다면,

구간 [1 ~ 4]의 합인 9와 구간 [5 ~ 6]의 합인 7인 16을 얻을 수 있다.

따라서 회색으로 표시된 node에 업데이트 할 필요가 없다.

---

lazy update

 

다시 구간 [1 ~ 6]까지 1을 더하는 과정을 차근차근히 진행해보자.

전체 구간 [1 ~ 7]에 대해 구간 [1 ~ 6]을 1씩 더해야 한다.

 

구간 [1 ~ 7]은 구간 [1 ~ 6]에 포함되지 않는다.

따라서 구간 [1 ~ 7]을 구간 [1 ~ 4]와 [5 ~ 7]로 나눈다.

 

구간 [1 ~ 4]는 구간 [1 ~ 6]에 포함된다.

따라서 구간 [1 ~ 4]는 +1이 node 1 ~ 4 만큼 증가하게 되므로,  (4 - 1 + 1) * 1 만큼 증가하게 된다.

구간 [1 ~ 4]의 원래 수는 5였으므로 5 + 4가 되어 9가 되고,

아래 노드인 구간 [1 ~ 2]와 구간 [3 ~ 4]의 node는 나중에 update 하기 위해 증가할 수 1로 체크만 해둔다. 

(구간이 [left ~ right]라면 left와 right가 다른 경우만 증가시킨다.)

 

그림으로 보면 아래와 같다.

 

구간 [1 ~ 2]와 구간 [3 ~ 4]에 표시된 (1)은 lazy 배열에 표시해둔다. 

lazy 배열은 tree로 따로 구성되며, tree의 index와 lazy의 index는 같다.

ll tree[4004000];
ll lazy[4004000];

 

다시 남은 구간 [5 ~ 7]을 보자.

구간 [5 ~ 7]은 구간 [1 ~ 6]에 포함되지 않는다.

따라서 구간 [5 ~ 7]은 구간 [5 ~ 6]과 구간 [7]로 나눈다.

 

구간 [5 ~ 6]은 구간 [1 ~ 6]에 포함되고, node는 2개(6 - 5 + 1)이므로 2를 증가시킨다.

그리고 바로 아래 node인 구간 [5]와 구간 [6]에 1로 표시해둔다.

 

구간 [7]은 구간 [1 ~ 6]에 포함되지 않으므로, 아무것도 하지 않고 종료한다.

 

구간 [5 ~ 6]과 구간 [7]의 작업이 완료되었으므로,

구간 [5 ~ 7]의 값을 구간 [5 ~ 6]의 값과 구간 [7]의 합으로 갱신하고 종료한다.

 

구간 [1 ~ 4]와 구간 [5 ~ 7]의 작업이 종료되었으므로 구간 [1 ~ 7]을 갱신하고 종료한다.

최종적으로 갱신된 node와 lazy는 다음과 같다. (lazy는 괄호가 있는 경우가 아니라면 모두 0이다.)

---

구간의 합

 

이제 구간 [1 ~ 6]의 합을 구해보자.

Top-Down Segment Tree의 getSum 방식으로 구할 수 있다.

구간 [1 ~ 6]은 구간 [1 ~ 4]와 구간 [5 ~ 6]의 합을 구하면 되므로, 아래의 node의 합인 9 + 7 = 16이 return된다.

→ 현재 상태에서, 구간 [1 ~ 6]은 lazy에 표시된 노드를 건드릴 필요가 없다.

 

이제 구간 [2 ~ 5]의 합을 구해보자.

실제 합은 3 + 4 + 2 + 3 = 12가 나와야 한다.

 

구간 [2 ~ 5]는 구간 [2] + 구간 [3 ~ 4] + 구간 [5]이므로 빨갛게 표시된 node의 합을 구해야 한다.

 

그런데 구간 [2]와 구간 [3 ~ 4]와 구간 [5]는 모두 아직 갱신되지 않았다.

 

이제, 구간을 갱신하면서 합을 구해보자.

 

구간 [1 ~ 7]은 구간 [2 ~ 5]에 포함되지 않는다.

따라서 구간 [1 ~ 4]와 구간 [5 ~ 7]로 나눈다.

 

구간 [1 ~ 4]도 구간 [2 ~ 5]에 포함되지 않으므로 구간 [1 ~ 2]와 구간 [3 ~ 4]로 나눈다.

같은 이유로 구간 [1  ~ 2]는 구간 [1]과 구간 [2]로 나눈다.

 

이때, 구간 [1 ~ 2]의 lazy에 1이 표시되어 있으므로 구간 [1 ~ 2]를 갱신한다.

 

구간 [1 ~ 2]는 node가 2개이므로 표시된 1에 2를 곱한 값을 더해서 3으로 변경한다.

3으로 갱신이 되었으므로 해당 node의 lazy는 0으로 바꾼다.

그리고 바로 아래의 node 2개에서 lazy를 1로 체크한다.

 

갱신이 완료되었으므로, 구간 [1 ~ 2]는 구간 [1]과 구간 [2]로 나눌 수 있다.

구간 [1]은 구간 [2 ~ 5]에 포함되지 않지만 이미 이 구간에 왔으므로 lazy = 1을 처리한다.

left와 right가 같기 때문에 아래 node에 lazy를 체크하지 않는다.

따라서 구간 [1]은 0으로 변경되었고, lazy = 0으로 변경한다.

 

구간 [2]에도 lazy가 체크되어 있으므로 갱신한다.

그리고 구간 [2]는 합을 구해야하는 [2 ~ 5] 구간에 포함되므로 더해지게 된다.

 

다시 구간 [3 ~ 4]로 이동하자.

lazy에 1이 체크되어 있으므로 갱신한다.

구간 [3 ~ 4]는 node가 2개이므로 2가 더해질 것이고, 아래 node의 lazy에 1을 체크한다.

 

그런데 구간 [3 ~ 4]는 합을 구해야 하는 구간 [2 ~ 5]에 포함된다.

따라서 더 이상 내려가지 않고 그대로 6을 return하면 된다.

 

이제 구간 [5 ~ 7]로 가보자.

구간 [5 ~ 7]은 구간 [2 ~ 5]에 포함되지 않는다.

따라서 구간 [5 ~ 6]과 구간 [7]로 나눈다.

 

마찬가지로, 구간 [5 ~ 6]은 lazy가 없기 때문에 아무것도 하지 않고, 구간 [5]와 구간 [6]으로 나눈다.

 

구간 [5]에는 lazy가 표시되어 있으므로 갱신한다.

그리고 구간 [5]는 구간 [2 ~ 5]에 포함되어 있으므로 3이 더해질 것이다.

 

구간 [6]은 구간 [2 ~ 5]에 포함되지 않지만, lazy는 표시되어 있으므로 온 김에 갱신 해둔다.

 

구간 [7]은 lazy도 없고 구간 [2 ~ 5]에 포함되지도 않으므로 그냥 넘어간다.

 

최종적으로 저장되는 tree와 lazy는 아래와 같고 구간 [2 ~ 5]의 합은 3 + 6 + 3 = 12를 return하게 된다.

---

구현

 

위의 설명대로 구현한 lazy_update는 다음과 같다.

node에 더할 때 각 node의 개수와 lazy에 적힌 값을 곱해서 누적하고, 아래 node에 lazy를 다시 체크한다.

갱신이 완료되면 해당 node의 lazy는 0으로 바꾼다.

void lazy_update(int left, int right, int node)
{
	if (lazy[node] == 0) return;

	tree[node] += (right - left + 1) * lazy[node];

	if (left != right)
	{
		lazy[node * 2] += lazy[node];
		lazy[node * 2 + 1] += lazy[node];
	}

	lazy[node] = 0;
}

 

Top-Down Segment Tree의 update는 index였지만 여기서는 구간을 갱신하므로 구간 [a ~ b]로 변경된다.

update를 하기 전에 lazy를 먼저 update하고 구간을 update 한다.

마지막에 tree의 node를 아래의 node의 합으로 갱신해야 한다.

void update(int left, int right, int node, int a, int b, ll diff)
{
	lazy_update(left, right, node);

	if (b < left || right < a) return;

	if (a <= left && right <= b)
	{
		tree[node] += (right - left + 1) * diff;
		if (left != right)
		{
			lazy[node * 2] += diff;
			lazy[node * 2 + 1] += diff;
		}

		return;
	}

	int mid = (left + right) / 2;

	update(left, mid, node * 2, a, b, diff);
	update(mid + 1, right, node * 2 + 1, a, b, diff);

	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

 

구간의 합을 구하는 함수는 lazy_update만 추가하면 된다.

ll getSum(int left, int right, int a, int b, int node)
{
	lazy_update(left, right, node);

	if (b < left || right < a) return 0;
	if (a <= left && right <= b) return tree[node];

	int mid = (left + right) / 2;

	return getSum(left, mid, a, b, node * 2) + getSum(mid + 1, right, a, b, node * 2 + 1);
}

 

전체 코드는 다음과 같다.

여기서도 tree는 주어진 N에 가장 2의 배수에 근접한 값의 2배로 잡으면 된다. (1,000,000 → 1,048,576 → 2,097,152)

메모리가 넉넉하다면 4배로 잡으면 충분하다. (lazy도 고려해야 한다.)

#include <stdio.h>

typedef long long int ll;

int N, M, K;
ll arr[1001000];
ll tree[4004000];
ll lazy[4004000];

ll init(int left, int right, int node)
{
	if (left == right) return tree[node] = arr[left];

	int mid = (left + right) / 2;

	return tree[node]
		= init(left, mid, node * 2) + init(mid + 1, right, node * 2 + 1);
}

void lazy_update(int left, int right, int node)
{
	if (lazy[node] == 0) return;

	tree[node] += (right - left + 1) * lazy[node];

	if (left != right)
	{
		lazy[node * 2] += lazy[node];
		lazy[node * 2 + 1] += lazy[node];
	}

	lazy[node] = 0;
}

void update(int left, int right, int node, int a, int b, ll diff)
{
	lazy_update(left, right, node);

	if (b < left || right < a) return;

	if (a <= left && right <= b)
	{
		tree[node] += (right - left + 1) * diff;
        
		if (left != right)
		{
			lazy[node * 2] += diff;
			lazy[node * 2 + 1] += diff;
		}

		return;
	}

	int mid = (left + right) / 2;

	update(left, mid, node * 2, a, b, diff);
	update(mid + 1, right, node * 2 + 1, a, b, diff);

	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

ll getSum(int left, int right, int a, int b, int node)
{
	lazy_update(left, right, node);

	if (b < left || right < a) return 0;
	if (a <= left && right <= b) return tree[node];

	int mid = (left + right) / 2;

	return getSum(left, mid, a, b, node * 2) + getSum(mid + 1, right, a, b, node * 2 + 1);
}

int main()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int i = 1; i <= N; i++) scanf("%lld", &arr[i]);

	init(1, N, 1);

	for (int i = 0; i < M + K; i++)
	{
		int a;

		scanf("%d", &a);

		if (a == 1)
		{
			int b, c;
			ll d;

			scanf("%d %d %lld", &b, &c, &d);

			update(1, N, 1, b, c, d);
		}
		else
		{
			int b, c;

			scanf("%d %d", &b, &c);

			printf("%lld\n", getSum(1, N, b, c, 1));
		}
	}

	return 0;
}