[ Algorithm ] 느리게 갱신되는 세그먼트 트리

도입

세그먼트 트리 이후 작성하는 알고리즘 튜토리얼 글입니다. 이 글은 세그먼트 트리의 응용 방식 중 하나인 Lazy Propagation in Segment Tree ( 느리게 갱신되는 세그먼트 트리 ) 에 대한 원리 및 응용 방식을 다루고 있으며, 이 글을 읽은 후 느리게 갱신되는 세그먼트 트리를 이용하여 여러 문제를 풀 수 있도록 하는 것이 이 글의 목적입니다. Lazy 값을 이용한 느린 전파 테크닉을 이해하여 추후 더 나아가 Segment Tree Beats 등을 배우면서 어려운 구간 쿼리를 해결하는 능력을 기를 수 있을 것입니다.

본 글은 C를 기반으로 작성되었습니다.

 

세그먼트 트리에 대한 이해가 필요합니다! https://readytojoin.tistory.com/57

[ Algorithm ] 세그먼트 트리

 

접근

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

10999번: 구간 합 구하기 2

다음과 같은 문제를 예시로 들어보자.

세그먼트 트리 튜토리얼 글에서 다루었던 구간 합 구하기 문제와는 다르게, 수의 변경이 일어날 때 여러 구간에 동시에 값을 더하거나 빼야 한다.

 

무한으로 즐겨요 세그먼트 트리

int mode;
scanf("%d", &mode);
if (mode == 1) {
    LL left, right, value;
    scanf("%lld %lld %lld", &left, &right, &value);
    for (int idx = left; idx <= right; idx++)
        update(1, n, 1, idx, value);
}

세그먼트 트리로 풀이한다면 솔루션이 얼핏 보이는 플래티넘 4 문제기에, 다음과 같이 left와 right 구간 안의 요소에 모두 value 만큼 update를 하나하나 진행해준다면 코드를 완성할 수 있다. 값도 제대로 도출된다! 그리고 싱글벙글 제출하면...

어라

1%에서 시간 초과 어택을 맞게 된다. 왜 시간 초과가 발생하는걸까?

 

시간 복잡도로 최악의 상황을 고려해보자. 세그먼트 트리에서 리프 노드 하나를 업데이트하기 위해 update 함수를 호출할 때 O(logN)이 걸린다. 문제에서 주어지는 수의 개수는 최대 1,000,000 개 이므로, 만약 수의 변경이 일어나는 최대 횟수인 10,000번 동안 1번째 수부터 1,000,000번째 수까지 값을 변경해야 한다면? 리프 노드를 하나하나씩 업데이트한다면 O(logN)이 1,000,000번 일어나고, 이 업데이트가 10,000번 일어나니... O(NlogN) X M 이라는 어마무시한 시간 복잡도와 함께 장렬하게 시간 초과를 받게 될 것이다. 어떻게 시간을 줄일 수 있을까?

 

최악의 상황에서는 1번째 수부터 1,000,000번째 수까지 계속 업데이트를 진행해야 한다. 구간의 합을 구할 때는 1번째 수부터 1,000,000번째 수까지 합을 구하려면 그냥 모든 구간이니 루트 노드에만 접근하면 합을 얻을 수 있었는데, 업데이트할 때는 하나하나 수행하려니 정말 지옥과 같은 상황이다.

구간 합을 구할 때 적은 트리 탐색이 일어났던 것처럼, 차라리 그 구간에 업데이트가 일어난 후의 결과를 미리 계산해놓고 빠져나온 다음, 미리 계산한 노드의 자식 노드에 나중에 접근할 때에 업데이트된 결과를 알려주는 방식이면 시간을 줄일 수 있지 않을까?

 

느리게 갱신되는 세그먼트 트리 ( Lazy Propagation in Segment Tree )

게으르게 전파되는 특징을 가진 Lazy 값을 이용하여 직접 접근하지 않는 구간에는 나중에 직접 접근할 때 값을 업데이트해주는, 특정 구간에 대한 업데이트를 유리하게 진행할 수 있는 아이디어를 Lazy Propagation in Segment Tree (느리게 갱신되는 세그먼트 트리) 라고 한다. 기본적인 트리 구성은 세그먼트 트리와 동일하고, Lazy 값이 추가되었다.

기존 세그먼트와는 달리 Lazy 값이 존재한다.

구현 방식 1

long long int arr[1000001];
long long int tree[4000004]; // Segment Tree
long long int lazy[4000004]; // Lazy Value

구현 방식 2 ( 세그먼트 트리 노드 안에 여러 정보가 필요할 때 구조체로 노드를 만들 수 있다. )

typedef struct _Node {
	long long value;
	long long lazy;
} Node;

Node tree[4000001];

 

느리게 갱신되는 세그먼트 트리의 특징은, 구간에 한꺼번에 업데이트를 진행해야 할 때 미리 그 구간의 업데이트 결과를 다 계산해놓고 구간의 자식 노드에는 알리지 않는다. ( 게으르게 업데이트 값이 전파된다. 아 귀찮아 나중에 갈래잉~ ) 이후 자식 노드에 직접 접근할 때 업데이트 결과를 알려 업데이트를 진행한다. 값이 느리게 전파되기 때문에 기존에 세그먼트 트리로 계속 업데이트를 진행했던 것과는 달리 접근 횟수 면에서 시간을 단축시킬 수 있다.

 

Lazy Propagation in Segment Tree - Update Range

예를 들어, 1번째 수부터 8번째 수까지 3을 더해야 하는 쿼리를 처리한다고 해보자.

트리 탐색 중 업데이트해야 하는 구간의 노드를 발견했다. 이때 이 구간에 모두 업데이트를 진행했다고 가정하고 결과 값을 구해야 한다! [1:5] 구간은 5개의 수를 가리키고 있기 때문에, 이 구간에 +3을 진행한다면 이 구간의 합은 기존보다 +15가 증가하게 된다!

구간 합을 업데이트했다면, 자식 노드까지 업데이트를 진행하지 않아도 나중에 [1:5] 구간의 구간 합을 구할 때 바로 구할 수 있다! 물론 [1:5] 구간만 계속 구하지 않고 [2:5]나 [3:4] 처럼 내부 구간만 구하고 싶을 때도 있기 때문에, 그 부분은 나중에 구하겠다고 하고 Lazy 값을 자식 노드에게 전달한다.

이렇게 Lazy 값만 전파해두고, '나중에 이 내부 구간 필요할 때 업데이트할게~' 라며 탐색을 종료하고 루트 노드로 되돌아간다. 다른 구간도 업데이트를 이어서 진행해 주자.

구간 업데이트가 진행됐다면, 루트 노드로 올라오면서 값을 업데이트하는 방식은 세그먼트 트리와 같다. ( 어차피 모든 구간을 업데이트한 것처럼 특정 구간에 대한 합을 미리 계산했기에, 더해도 아무 문제가 없다! )

직접 리프 노드를 업데이트 하지 않아도 추후에 업데이트할 것이라고 Lazy 값을 전파했기 때문에, 업데이트 횟수를 크게 줄일 수 있다는 장점이 있다!

이 과정을 코드로 표현하면 다음과 같다.

void update_range(int start, int end, int idx, int left, int right, long long value) {
	push(start, end, idx); // 이후 설명
	if (end < left || right < start) return; // 구간 벗어나면 종료
	if (left <= start && end <= right) { // 구간 안일 시
    	// 업데이트 값 x 구간 크기 만큼 구간의 합을 미리 갱신하기
		tree[idx] += (end - start + 1) * value; 
        // 만약 리프 노드가 아니라면 자식 노드로 Lazy 값 전파하기
		if (start != end) {
			lazy[idx * 2] += value;
			lazy[idx * 2 + 1] += value;
		}
		return;
	}

	int mid = (start + end) / 2;
	update_range(start, mid, idx * 2, left, right, value);
	update_range(mid + 1, end, idx * 2 + 1, left, right, value); 
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]; // 업데이트
}

기존 세그먼트 트리에서 볼 수 있었던 update 함수와는 달리 push 함수가 존재한다. lazy 값을 추가해줌으로써 해주어야 하는 처리 중 하나인데, 다음 소제목에서 설명한다.

 

tree[idx] += (end - start + 1) * value;

업데이트하고 싶은 구간 안의 노드라면, (end - start + 1)로 구간의 크기를 구해 업데이트 하고 싶은 값과 곱함으로써 그 구간에 모두 업데이트를 한 것처럼 합을 미리 구한다. 

 

lazy[idx * 2] += value; lazy[idx * 2 + 1] += value;

만약 리프 노드가 아니라면, 더 업데이트 될 자식 노드가 존재하므로 자식 노드에게 value 만큼 업데이트가 될 것이라고 lazy 값을 value만큼 자식 노드에게 전파해준다.  

 

Lazy Propagation in Segment Tree - push

Range Update 과정에서 갑자기 push 함수가 등장한 것을 볼 수 있다. push 함수의 역할은 현재 노드에 lazy 값이 있다면 먼저 처리해주는 것이다.  이전에 전파해둔 lazy 값이 등장할 때, 다음 업데이트를 진행하려면 미리 lazy 값을 처리하여 계산해놓고 자식 노드로 전파를 해 놓아야 한다.

void push(int start, int end, int idx) {
	if (lazy[idx] != 0) {
		tree[idx] += (end - start + 1) * lazy[idx];
		if (start != end) {
			lazy[idx * 2] += lazy[idx];
			lazy[idx * 2 + 1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}

push 함수는 만약 지금 노드에 lazy 값이 0이 아니라면 ( 더하거나 빼야 하는 lazy 값이 존재한다면 ) update_range 함수에서 계산했던 것처럼 구간의 합을 크기만큼 계산하고 또 lazy 값을 전파한다.

또한, 이 노드에서 lazy 값에 대한 계산을 완료했으니 lazy 값을 0으로 초기화해준다.

 

push 는 어떤 상황에서 사용될까? 만약 [1:8] 구간에 +3 업데이트를 진행한 후 [1:4] 구간에 -2 업데이트를 진행한다고 해보자.

순조롭게 구간 업데이트를 위한 탐색이 진행되던 도중, Lazy 값이 0이 아닌 노드를 발견했다.

Lazy 값이 0이 아닌 노드는 부모 노드에서 구간 합을 미리 구한 뒤 자식 노드에 접근하지 않고 Lazy 값만 전파해줬음을 뜻하며, 이 노드에서 값 업데이트가 필요함을 의미한다.

push 함수를 이용해 해당 구간에 대한 합도 구하고 자식 노드에 lazy 값을 똑같이 전파하도록 하자. ( 자식 노드도 똑같이 값 업데이트가 필요하기 때문이다. )

push 함수를 이용해 lazy 값 계산이 완료되었다면, 기존에 쌓인 lazy 값은 0으로 초기화해준다.

이런 방식으로 계속해서 -2 업데이트를 진행해준다.

lazy 값은 기존에 업데이트했을 때 누적된 lazy 값에 누적된다. ( +3을 업데이트하고 -3을 업데이트하면 lazy 값이 0이 되므로 아무런 변화가 일어나지 않는 것처럼, 특정 구간에 여러 번 업데이트가 일어날 때 lazy 값이 누적될 수 있다! )

따라서 lazy 값을 +3으로 가지고 있던 4번 노드의 자식 노드들은 -2 업데이트로 인해 lazy 값이 +1이 된다.

구간 업데이트가 완료되었으니, 루트 노드로 돌아오면서 세그먼트 트리를 업데이트해준다.

이처럼 update_range 함수와 push 함수를 이용해, 특정 구간에 대한 여러 업데이트를 쉽게 처리할 수 있는 것이 가능해진다.

Lazy Propagation in Segment Tree - Interval Sum

구간의 합을 구하는 함수는 기존 세그먼트 트리와 동일하다. 이전 업데이트로 인해 lazy 값이 노드에 쌓여있을 수 있으니 push 함수를 먼저 수행해야 한다.

long long interval_sum(int start, int end, int idx, int left, int right) {
	push(start, end, idx);
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return tree[idx];

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

---

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

10999번: 구간 합 구하기 2

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

10999번: 구간 합 구하기 2

느리게 갱신되는 세그먼트 트리를 연습할 수 있는 문제이다. 수의 개수와 자료형에 유의하여 느리게 갱신되는 세그먼트 트리를 작성하자.

#include <stdio.h>
#define SIZE 1000001
typedef long long LL;

LL arr[SIZE];
LL tree[SIZE * 4];
LL lazy[SIZE * 4];

void build(int start, int end, int idx) {
	if (start == end) {
		tree[idx] = arr[start];
		lazy[idx] = 0;
		return;
	}

	int mid = (start + end) / 2;
	build(start, mid, idx * 2);
	build(mid + 1, end, idx * 2 + 1);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
	lazy[idx] = 0;
}

void push(int start, int end, int idx) {
	if (lazy[idx] != 0) {
		tree[idx] += (end - start + 1) * lazy[idx];
		if (start != end) {
			lazy[idx * 2] += lazy[idx];
			lazy[idx * 2 + 1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}

void update_range(int start, int end, int idx, int left, int right, LL value) {
	push(start, end, idx);
	if (end < left || right < start) return;
	if (left <= start && end <= right) {
		tree[idx] += (end - start + 1) * value;
		if (start != end) {
			lazy[idx * 2] += value;
			lazy[idx * 2 + 1] += value;
		}
		return;
	}

	int mid = (start + end) / 2;
	update_range(start, mid, idx * 2, left, right, value);
	update_range(mid + 1, end, idx * 2 + 1, left, right, value); 
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

LL interval_sum(int start, int end, int idx, int left, int right) {
	push(start, end, idx);
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return tree[idx];

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

int main(void) {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);

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

	build(1, n, 1);

	for (int i = 0; i < m + k; i++) {
		int mode, left, right;
		scanf("%d %d %d", &mode, &left, &right);
		if (mode == 1) {
			LL value;
			scanf("%lld", &value);
			update_range(1, n, 1, left, right, value);
		}
		else {
			printf("%lld\n", interval_sum(1, n, 1, left, right));
		}
	}
	return 0;
}

1395번: 스위치

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

1395번: 스위치

특정 구간에 있는 스위치를 모두 반전시키는 문제이다. 스위치를 모두 반전시키기 위해서는 (해당 구간의 크기) - (켜진 스위치 수) 로 트리를 업데이트하면 구간의 스위치를 모두 반전시킬 수 있는 아이디어 문제이다. 특정 구간에 스위치를 짝수번 반전시키면 결과가 동일하다는 것도 파악하면 lazy 값을 누적시키지 않고도 쉽게 lazy 값을 구성할 수 있다.

#include <stdio.h>
#define SIZE 100001

int tree[SIZE * 4] = { 0, };
int lazy[SIZE * 4] = { 0, };

void push(int start, int end, int idx) {
	if (lazy[idx] != 0) {
		tree[idx] = (end - start + 1) - tree[idx];
		if (start != end) {
			lazy[idx * 2] = (lazy[idx * 2] + 1) % 2;
			lazy[idx * 2 + 1] = (lazy[idx * 2 + 1] + 1) % 2;
		}
		lazy[idx] = 0;
	}
}

void update_range(int start, int end, int idx, int left, int right) {
	push(start, end, idx);
	if (end < left || right < start) return;
	if (left <= start && end <= right) {
		tree[idx] = (end - start + 1) - tree[idx];
		if (start != end) {
			lazy[idx * 2] = (lazy[idx * 2] + 1) % 2;
			lazy[idx * 2 + 1] = (lazy[idx * 2 + 1] + 1) % 2;
		}
		return;
	}

	int mid = (start + end) / 2;
	update_range(start, mid, idx * 2, left, right);
	update_range(mid + 1, end, idx * 2 + 1, left, right);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

int interval_sum(int start, int end, int idx, int left, int right) {
	push(start, end, idx);
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return tree[idx];

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

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	while (m--) {
		int o, s, t;
		scanf("%d %d %d", &o, &s, &t);
		if (o == 0) {
			update_range(1, n, 1, s, t);
		}
		else { // o == 1
			printf("%d\n", interval_sum(1, n, 1, s, t));
		}
	}
	return 0;
}

느리게 갱신되는 세그먼트 트리를 이용한 기초 문제를 풀어보았다. 이 아이디어를 이용하여 풀 수 있는 난이도 있는 문제가 많으니, 계속 풀어보면서 감을 잡는 것이 좋다고 생각한다.

다른 느리게 갱신되는 세그먼트 트리 문제의 풀이는 #lazy-propagation 에서 확인할 수 있다.

https://readytojoin.tistory.com/tag/lazy-propagation

공작소