[ Algorithm ] 세그먼트 트리

도입

이 글은 세그먼트 트리를 처음 접하거나, 세그먼트 트리의 기초적인 응용에 대한 solution idea를 얻고 싶은 분들을 위하여 제가 세그먼트 트리 태그를 풀면서 정립한 세그먼트 트리 개념을 설명하는 글입니다. 이 글을 읽은 뒤 세그먼트 트리의 기본적인 사용법을 익히고 기초 응용 문제를 풀 수 있도록 하는 것이 이 글의 목적입니다. 기초적인 응용 이후에 세그먼트 트리에 관련한 여러 응용 문제를 직접 풀어본다면, 세그먼트 트리를 깊이 이해하며 트리 구조를 변형할 수 있는 능력을 기름과 동시에 추후 Lazy Propagation with Segment Tree, Persistent Segment Tree 등의 알고리즘에 대한 배경 지식을 얻을 수 있을 것입니다.

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

 

접근

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

2042번: 구간 합 구하기

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

 

간단하지만 느린 원리로 구현해보기

수열 A가 주어지고 입력으로 여러 줄의 L, R이 들어올 때, 주어진 L, R에 맞는 A[L] + A[L+1] + A[L+2] + ... + A[R-2] + A[R-1] + A[R} 을 출력해야 한다면 다음과 같이 구현할 수 있다.

 

단순히 접근하면 A 수열의 L 번째 요소 부터 시작해서 A 수열의 R 번째까지의 요소까지 더하면 된다.

int L, R;
scanf("%d %d", &L, &R);

int result = 0;
for(int idx = L; idx <= R; idx++) // A[L] + A[L+1] + ... + A[R-1] + A[R]
    result += A[idx];

printf("%d", result);

중간중간 수열의 어떤 요소가 바뀌어야 한다면 그때그때마다 바꾸면 되니 편하게 구현할 수 있을 것이다.

하지만, 문제에서 주어진 수열의 길이는 최대 1,000,000 개이다. 최악의 상황을 생각해봤을 때 입력으로 들어오는 L, R이 모두 1, 1000000 이라면?

무무슨

시간 초과

for 반복문에서 idx 변수가 1부터 시작해서 1,000,000까지 반복하는 동안 구간의 합을 구하기 위해 요소를 하나하나씩 더해가면서 총 1,000,000번 연산을 한다고 해보자. 합을 구하는 횟수도 10,000번이나 일어난다면 연산은 10,000,000,000 번이 일어나게 되고.. O(NM) 으로 시간 초과를 발생시킬 수 있다.

 

차라리 누적 합 알고리즘을 이용해서 구간의 합을 미리 구해놓으면 어떨까?! 하는 기발한 방식을 떠올릴 순 있겠으나...

수열이 중간중간마다 변경될 수 있으니 최악의 경우 전체 요소의 누적 합을 계속 수정해야 하므로 비효율적이다.

 

변경될 가능성이 있는 연속적인 데이터에서 특정한 범위의 합, 곱, 최댓값, 최솟값 등을 계산해야 할 때, 세그먼트 트리는 이러한 상황을 계산할 수 있는 방법 중 하나가 될 것이다.

 

세그먼트 트리 (Segment Tree)

세그먼트 트리는 연속적으로 나열된 데이터에서 특정 범위의 합, 곱, 최댓값, 최솟값 등을 O(logN) 만에 빠르고 간단하게 구할 수 있는 자료 구조이다.  세그먼트 트리는 연속된 데이터의 배열 구조를 완전 이진 트리로 표현하며, 한 노드에서 일정 구간의 정보를 담고 있기에 하나하나 요소에 접근하지 않아도 바로 특정 구간의 정보를 얻을 수 있다.

Array : [L:R] -> L번째 요소부터 R번째 요소까지의 합

세그먼트 트리의 특징은 부모 노드가 자식 노드 데이터를 모아서 저장하고 있다는 것이다. 중간점을 이용해 트리를 이진 트리로 나누면서, 노드가 담당하는 구간도 나누었다. 먼저, 배열의 요소들은 트리의 리프 노드에 들어간다. 

리프 노드에 들어간 배열의 요소들

왼쪽 자식 노드의 값과 오른쪽 자식 노드의 값을 더한 결과는 부모 노드에 저장된다.

 

예를 들면 그림에서, 배열의 1번째 요소인 10 (Tree[16]) 과 배열의 2번째 요소인 5 (Tree[17]) 은 Tree[8]의 자식 노드이다.

1번째 요소부터 1번째 요소까지의 구간의 합을 저장한 10과 2번째 요소부터 2번째 요소까지의 구간의 합을 저장한 5를 더하면, 1번째 요소부터 2번째 요소까지의 구간의 합을 저장한 노드가 된다.

 

( 트리 이론 : 여기서, 부모 노드에서 자식 노드에 접근하려면 tree[idx * 2], tree[idx * 2 + 1] 로 접근이 가능하고, 자식 노드에서 부모 노드로 접근하려면 tree[idx / 2] 로 접근이 가능하다. )

16번째 노드와 17번째 노드의 합이 8번째 노드에 저장된다.

이와 같은 방식으로 왼쪽 구간과 오른쪽 구간을 더해 특정 구간의 정보를 저장하는 것이 세그먼트 트리이다.

배열의 데이터가 n개라면 세그먼트 트리 노드의 개수는 h 레벨까지 2^h - 1 개까지 발생하나, n * 4로 간편하게 선언할 수도 있다.

int arr[SIZE];
int tree[SIZE * 4];

Segment Tree - Build

세그먼트 트리에서 구간의 정보가 저장되는 원리를 알았으니, 세그먼트 트리를 직접 구성해 볼 것이다.

초기 상태

배열의 데이터를 세그먼트 트리에 저장하기 위해 초기 상태부터 시작할 것이다. 트리의 루트 노드 ( Tree[1] ) 는 배열의 전체 구간의 합 정보를 저장한다. 즉, 루트 노드가 저장하는 정보의 구간은 배열의 1번째 요소 (맨 처음) 부터 10번째 요소 (맨 끝) 이다. 편의상 노드가 표현하는 구간의 시작 부분과 끝 부분은 Start, End 로 표기한다.

노드의 구간 크기 ( End - Start + 1 ) 가 2 이상이라면, 해당 노드는 최소 2개 이상의 요소를 가진 구간을 저장하고 있다는 뜻이고, 최종적으로 1개의 요소만을 가리키기 위해 분할을 해야 한다. Mid = (Start + End) / 2 식을 이용하여 중간값을 구하고, 중간값을 기준으로  왼쪽 자식 노드는 [ Start : Mid ] 의 구간을, 오른쪽 자식 노드는 [ Mid + 1 : End } 의 구간을 저장한다. 이후 구간 크기가 1이 될 때 까지 -> ( End - Start + 1 = 1 ) 즉, 1개의 노드만을 가리킬 때까지 구간을 분할한다.

구간 안에 1개의 요소밖에 없는 노드 발견

분할을 지속하다가 구간의 크기가 1인 노드까지 도달했다면, 분할을 중단하고 배열의 데이터를 저장해야 한다. ( ex. 3번째 요소부터 3번째 요소까지의 구간의 합은 3번째 요소의 값과 같다. )

아직 전부 분할하지 않은 노드는 계속해서 분할 한다.

배열 데이터 저장 완료

배열의 데이터를 모두 저장했다면, 이제 루트 노드로 돌아오면서 왼쪽 노드와 오른쪽 노드를 합하면서 구간의 합을 재귀적으로 구해야 한다.

 

루트 노드까지 구간의 합을 모두 저장한 후, 세그먼트 트리 초기화가 완료되었다.

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

void build(int start, int end, int idx) {
	if (start == end) {
		// 리프 노드라면 배열의 데이터 저장 
		tree[idx] = arr[start];
		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]; 
}

// in main()
// 루트 노드인 Array[1:N], Tree[1] 부터 시작
build(1, n, 1);

build 함수와 함께 이후에 다룰 interval_sum, update 함수 모두 재귀적으로 이루어진다.

트리의 자식 노드로 탐색을 계속하면서 자식 노드를 만날 때까지 끝까지 들어가는 재귀를 사용하면, 간결한 코드로 트리를 탐색할 수 있는 효과를 얻을 수 있다.

build 함수 디버그 과정

구현에서 주의할 점은, build 함수의 Start와 End가 각각 1과 n이기에, 배열의 데이터도 0번째 인덱스가 아닌 1번째 인덱스부터 저장해야 tree[idx] = arr[start] 에서 배열이 밀리지 않고 start 번째 인덱스를 잘 저장한다.

디버그 과정을 살펴보면, (1) 왼쪽 구간 탐색 (2) 오른쪽 구간 탐색 (3) 노드 업데이트 과정으로 트리가 build 되는 것을 확인할 수 있다.

 

> 사용한 디버그 함수

void build(int start, int end, int idx) {
	printf("build 함수 실행. Array[%d-%d] Tree[%d]\n", start, end, idx);
	if (start == end) {
		tree[idx] = arr[start];
		printf("Start와 End가 동일. Tree[%d] = %d\n\n", idx, tree[idx]);
		return;
	}
	
	int mid = (start + end) / 2;
	printf("[%d-%d]의 왼쪽 자식 노드 탐색 -> [%d-%d]\n\n", start, end, start, mid);
	build(start, mid, idx * 2);
	printf("[%d-%d]의 오른쪽 자식 노드 탐색 -> [%d-%d]\n\n", start, end, mid + 1, end);
	build(mid + 1, end, idx * 2 + 1);
	
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
	printf("[%d-%d] 의 값 계산 : %d ( %d + %d )\n\n", start, end, tree[idx], tree[idx * 2], tree[idx * 2 + 1]);
}

> 실행 결과

build 함수 실행. Array[1-10] Tree[1]
[1-10]의 왼쪽 자식 노드 탐색 -> [1-5]

build 함수 실행. Array[1-5] Tree[2]
[1-5]의 왼쪽 자식 노드 탐색 -> [1-3]

build 함수 실행. Array[1-3] Tree[4]
[1-3]의 왼쪽 자식 노드 탐색 -> [1-2]

build 함수 실행. Array[1-2] Tree[8]
[1-2]의 왼쪽 자식 노드 탐색 -> [1-1]

build 함수 실행. Array[1-1] Tree[16]
Start와 End가 동일. Tree[16] = 10

[1-2]의 오른쪽 자식 노드 탐색 -> [2-2]

build 함수 실행. Array[2-2] Tree[17]
Start와 End가 동일. Tree[17] = 5

[1-2] 의 값 계산 : 15 ( 10 + 5 )

[1-3]의 오른쪽 자식 노드 탐색 -> [3-3]

build 함수 실행. Array[3-3] Tree[9]
Start와 End가 동일. Tree[9] = 4

[1-3] 의 값 계산 : 19 ( 15 + 4 )

[1-5]의 오른쪽 자식 노드 탐색 -> [4-5]

build 함수 실행. Array[4-5] Tree[5]
[4-5]의 왼쪽 자식 노드 탐색 -> [4-4]

build 함수 실행. Array[4-4] Tree[10]
Start와 End가 동일. Tree[10] = 3

[4-5]의 오른쪽 자식 노드 탐색 -> [5-5]

build 함수 실행. Array[5-5] Tree[11]
Start와 End가 동일. Tree[11] = 7

[4-5] 의 값 계산 : 10 ( 3 + 7 )

[1-5] 의 값 계산 : 29 ( 19 + 10 )

[1-10]의 오른쪽 자식 노드 탐색 -> [6-10]

build 함수 실행. Array[6-10] Tree[3]
[6-10]의 왼쪽 자식 노드 탐색 -> [6-8]

build 함수 실행. Array[6-8] Tree[6]
[6-8]의 왼쪽 자식 노드 탐색 -> [6-7]

build 함수 실행. Array[6-7] Tree[12]
[6-7]의 왼쪽 자식 노드 탐색 -> [6-6]

build 함수 실행. Array[6-6] Tree[24]
Start와 End가 동일. Tree[24] = 6

[6-7]의 오른쪽 자식 노드 탐색 -> [7-7]

build 함수 실행. Array[7-7] Tree[25]
Start와 End가 동일. Tree[25] = 4

[6-7] 의 값 계산 : 10 ( 6 + 4 )

[6-8]의 오른쪽 자식 노드 탐색 -> [8-8]

build 함수 실행. Array[8-8] Tree[13]
Start와 End가 동일. Tree[13] = 1

[6-8] 의 값 계산 : 11 ( 10 + 1 )

[6-10]의 오른쪽 자식 노드 탐색 -> [9-10]

build 함수 실행. Array[9-10] Tree[7]
[9-10]의 왼쪽 자식 노드 탐색 -> [9-9]

build 함수 실행. Array[9-9] Tree[14]
Start와 End가 동일. Tree[14] = 9

[9-10]의 오른쪽 자식 노드 탐색 -> [10-10]

build 함수 실행. Array[10-10] Tree[15]
Start와 End가 동일. Tree[15] = 4

[9-10] 의 값 계산 : 13 ( 9 + 4 )

[6-10] 의 값 계산 : 24 ( 11 + 13 )

[1-10] 의 값 계산 : 53 ( 29 + 24 )

Segment Tree - Interval Sum

구성한 세그먼트 트리로 특정 구간의 합을 구할 것이다.

본래 O(NM) 의 순차적 계산 방법과는 다르게, 세그먼트 트리는 이미 구해진 구간들을 조합해 빠르게 구간의 정보를 획득할 수 있다. 루트 노드부터 시작해서, 만약 해당 노드가 내가 원하는 구간을 포함하고 있으면 자식 노드로 들어가 자세하게 구간을 획득한다.

L이 3이고 R이 9인 구간의 합을 구해보자. 

만약 내가 원하는 구간의 일부를 가지고 있는 노드라면, 더 이상 자식 노드로 들어가지 않고 그 노드의 합만 가져가면 된다. 즉, 배열 요소를 하나하나 더하지 않고도 이미 구해놓은 구간을 더해 빠르게 연산이 가능하다.

내가 원하는 구간의 정보를 세그먼트 트리에서 모두 얻었다면, 루트 노드로 돌아오면서 얻어낸 값만 더해 내가 원하는 구간 합을 구한다.

이렇게 [3:9] 구간의 합은 34임을 얻을 수 있다.

 

만약 내가 이미 구해놓은 구간이라면 더 빨리 구간 합을 얻을 수 있다. 예를 들어 [1:10]의 구간의 합을 얻고 싶다면.. 

루트 노드에서 정보만 가져와서 한번에 구할 수 있다.

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

int interval_sum(int start, int end, int idx, int left, int right) {
	// 만약 구간을 벗어났다면, 아무것도 더하지 않는 0 반환
	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);
}

// in - main()
// 루트 노드인 Array[1:N], Tree[1] 부터 시작
printf("%d", interval_sum(1, n, 1, L, R));

interval_sum 함수 디버그 과정

> 사용한 디버그 함수

int interval_sum(int start, int end, int idx, int left, int right) {
	printf("[%d-%d] interval_sum \n", start, end);
	if (end < left || right < start) {
		printf("[%d-%d] 는 구하려는 [%d-%d] 구간을 벗어남. 종료\n\n", start, end, left, right);
		return 0;
	}
	if (left <= start && end <= right) {
		printf("[%d-%d] 는 구하려는 [%d-%d] 구간의 일부! %d 반환 \n\n",start, end, left, right, tree[idx]);
		return tree[idx];
	}
	
	int mid = (start + end) / 2;
	int r1 = interval_sum(start, mid, idx*2, left, right);
	int r2 = interval_sum(mid+1, end, idx*2+1, left, right);
	int r3 = r1 + r2;
	printf("[%d-%d] %d + [%d-%d] %d => %d 반환\n\n", start, mid, r1, mid+1, end, r2, r3);
	return r3;
}

> 실행 결과

[1-10] interval_sum
[1-5] interval_sum
[1-3] interval_sum
[1-2] interval_sum
[1-2] 는 구하려는 [3-9] 구간을 벗어남. 종료

[3-3] interval_sum
[3-3] 는 구하려는 [3-9] 구간의 일부! 4 반환

[1-2] 0 + [3-3] 4 => 4 반환

[4-5] interval_sum
[4-5] 는 구하려는 [3-9] 구간의 일부! 10 반환

[1-3] 4 + [4-5] 10 => 14 반환

[6-10] interval_sum
[6-8] interval_sum
[6-8] 는 구하려는 [3-9] 구간의 일부! 11 반환

[9-10] interval_sum
[9-9] interval_sum
[9-9] 는 구하려는 [3-9] 구간의 일부! 9 반환

[10-10] interval_sum
[10-10] 는 구하려는 [3-9] 구간을 벗어남. 종료

[9-9] 9 + [10-10] 0 => 9 반환

[6-8] 11 + [9-10] 9 => 20 반환

[1-5] 14 + [6-10] 20 => 34 반환

[3:9] = 34

Segment Tree - Update

세그먼트 트리의 꽃, 업데이트 함수이다. 누적 합 알고리즘을 사용하기 버거운 이유는 수열의 요소가 중간중간 변경되기 때문이다. 근데 세그먼트 트리도 이미 구간 합을 다 구해놨는데 결국 다 바꿔야되는거 아니냐? 생각할 수 있겠으나, 

한 요소의 값을 변경한다면 그 요소와 관련된 구간만 변경하면 되는데, 이 또한 재귀적으로 변경이 가능하다.

3번째 요소의 데이터를 15로 변경해보자. 루트 노드부터 시작해서 3번째 요소를 찾을 때 까지 리프 노드로 내려가자.

트리에서 특정 요소를 찾을 때까지 트리에 진입한 뒤, 루트 노드로 되돌아갈 때 구간 합을 업데이트 해주면 특정 요소와 관련된 구간의 합이 업데이트되면서 간편하게 트리를 갱신해줄 수 있다. 리프 노드를 갱신하고 루트 노드로 되돌아가면서 자식 노드를 다시 더해서 값을 갱신해 가자.

 

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

void update(int start, int end, int idx, int what, int value) {
	// 특정 요소를 포함하지 않는 구간일 때 종료
	if (what < start || end < what) return;

	// 리프 노드까지 도착했을 때 변경하고자 하는 value 값으로 업데이트
	if (start == end) {
		tree[idx] = value;
		return;
	}

	int mid = (start + end) / 2;
	update(start, mid, idx * 2, what, value);
	update(mid + 1, end, idx * 2 + 1, what, value);

	// 루트 노드로 돌아오면서 관련된 노드들 갱신하기
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

// in - main()
// 루트 노드인 Array[1:N], Tree[1] 부터 시작
update(1, N, 1, 3, 15);

Update 함수 디버그 과정

> 사용한 디버그 함수

void update(int start, int end, int idx, int what, int value) {
	printf("[%d-%d] update \n", start, end);
	if (what < start || end < what) {
		printf("[%d-%d]는 [%d] 을 벗어남. 종료\n\n", start, end, what);
		return;
	}
	
	printf("[%d-%d]는 [%d] 구간을 포함함.\n", start, end, what);
	if (start == end) {
		printf("[%d-%d] 발견! tree[%d] : %d -> %d \n\n", start, end, idx, tree[idx], value);
		tree[idx] = value;
		return;
	}
	
	int mid = (start + end) / 2;
	update(start, mid, idx * 2, what, value);
	update(mid + 1, end, idx * 2 + 1, what, value);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
	printf("[%d-%d] : ( [%d-%d] %d + [%d-%d] %d ) = %d\n\n", start, end, start, mid, tree[idx * 2], mid + 1, end, tree[idx * 2 + 1], tree[idx]);
}

> 실행 결과

[1-10] update
[1-10]는 [3] 구간을 포함함.
[1-5] update
[1-5]는 [3] 구간을 포함함.
[1-3] update
[1-3]는 [3] 구간을 포함함.
[1-2] update
[1-2]는 [3] 을 벗어남. 종료

[3-3] update
[3-3]는 [3] 구간을 포함함.
[3-3] 발견! tree[9] : 4 -> 15

[1-3] : ( [1-2] 15 + [3-3] 15 ) = 30

[4-5] update
[4-5]는 [3] 을 벗어남. 종료

[1-5] : ( [1-3] 30 + [4-5] 10 ) = 40

[6-10] update
[6-10]는 [3] 을 벗어남. 종료

[1-10] : ( [1-5] 40 + [6-10] 24 ) = 64

이제 세그먼트 트리의 기본적인 기능을 이용하여 문제를 풀어보자.

 

2042번: 구간 합 구하기

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

2042번: 구간 합 구하기

세그먼트 트리의 기초적인 사용으로 풀이할 수 있는 문제이다. 입력 기준을 확인한 후 세그먼트 트리를 작성하자.

#include <stdio.h>

// Array, Tree 사이즈 지정
#define SIZE 1000000

// 편의상 사용
typedef long long LL;

LL arr[SIZE]; // 배열
LL tree[SIZE * 4]; // 세그먼트 트리

void build(int start, int end, int idx) {
	if (start == end) {
		tree[idx] = arr[start];
		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];
}

void update(int start, int end, int idx, int what, LL value) {
	if (what < start || end < what) return;
	if (start == end) {
		tree[idx] = value;
		return;
	}

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

LL interval_sum(int start, int end, int idx, int left, int right) {
	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 = 0; i < n; i++)
		scanf("%lld", &arr[i]);

	// 세그먼트 트리 초기화
	build(0, n - 1, 1);

	/*
	build(0, n - 1, 1) -> 수가 arr[0] ~ arr[n-1]에 저장되었을 때 사용
	build(1, n, 1) -> 수가 arr[1] ~ arr[n]에 저장되었을 때 사용
	*/

	// 수 변경, 구간 합 구하기 수행
	for (int i = 0; i < m + k; i++) {
		int mode;
		scanf("%d", &mode);

		if (mode == 1) { // 수 변경
			int b;
			LL c;
			scanf("%d %lld", &b, &c);

			update(0, n - 1, 1, b - 1, c);
			/*
			update(0, n - 1, 1, b - 1, c) -> 수가 arr[0] ~ arr[b-1] ~ arr[n-1]에 저장되었을 때 사용
			update(1, n, 1, b, c) -> 수가 arr[1] ~ arr[b] ~ arr[n]에 저장되었을 때 사용
			*/
		}
		else { // mode == 2 - 구간 합 구하기
			int b, c;
			scanf("%d %d", &b, &c);
			printf("%lld\n", interval_sum(0, n - 1, 1, b - 1, c - 1));
			/*
			interval_sum(0, n - 1, 1, b - 1, c - 1) -> 수가 arr[0] ~ arr[b-1] ~ arr[c-1] ~ arr[n-1]에 저장되었을 때 사용
			interval_sum(1, n, 1, b, c) -> 수가 arr[1] ~ arr[b] ~ arr[c] ~ arr[n]에 저장되었을 때 사용
			*/
		}
	}
	return 0;
}

2357번: 최솟값과 최댓값

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

2357번: 최솟값과 최댓값

세그먼트 트리로 최솟값과 최댓값을 구하는 예제이다. 지금까지 사용한 세그먼트 트리가 구간의 "합"을 저장해줬다면, 이번엔 구간의 "최댓값"을 구하는 세그먼트 트리와 구간의 "최솟값"을 구하는 세그먼트 트리를 만들면 된다.

도중에 수열의 요소를 바꾸는 행위가 없으니, build 함수와 interval_sum 함수를 최댓값을 구하는 함수와 최솟값을 구하는 함수로 개조해서 사용하면 된다.

Before : tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];

After : tree[idx] = (tree[idx * 2] > tree[idx * 2 + 1] ? tree[idx * 2] : tree[idx * 2 + 1]);

#include <stdio.h>
#define SIZE 100000
#define MIN_OVER 0
#define MAX_OVER 1000000001

int arr[SIZE];
int min_tree[SIZE * 4];
int max_tree[SIZE * 4];

void min_build(int start, int end, int idx) {
	if (start == end) {
		min_tree[idx] = arr[start];
		return;
	}

	int mid = (start + end) / 2;
	min_build(start, mid, idx * 2);
	min_build(mid + 1, end, idx * 2 + 1);

	min_tree[idx] = (min_tree[idx * 2] < min_tree[idx * 2 + 1] ? min_tree[idx * 2] : min_tree[idx * 2 + 1]);
}
void max_build(int start, int end, int idx) {
	if (start == end) {
		max_tree[idx] = arr[start];
		return;
	}

	int mid = (start + end) / 2;
	max_build(start, mid, idx * 2);
	max_build(mid + 1, end, idx * 2 + 1);

	max_tree[idx] = (max_tree[idx * 2] > max_tree[idx * 2 + 1] ? max_tree[idx * 2] : max_tree[idx * 2 + 1]);
}

int find_min(int start, int end, int idx, int left, int right) {
	if (end < left || right < start) return MAX_OVER;
	if (left <= start && end <= right) return min_tree[idx];

	int mid = (start + end) / 2;
	int n1 = find_min(start, mid, idx * 2, left, right);
	int n2 = find_min(mid + 1, end, idx * 2 + 1, left, right);

	return (n1 < n2 ? n1 : n2);
}

int find_max(int start, int end, int idx, int left, int right) {
	if (end < left || right < start) return MIN_OVER;
	if (left <= start && end <= right) return max_tree[idx];

	int mid = (start + end) / 2;
	int n1 = find_max(start, mid, idx * 2, left, right);
	int n2 = find_max(mid + 1, end, idx * 2 + 1, left, right);

	return (n1 > n2 ? n1 : n2);
}

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

	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	min_build(0, n - 1, 1);
	max_build(0, n - 1, 1);

	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);

		printf("%d %d\n", find_min(0, n - 1, 1, a - 1, b - 1), find_max(0, n - 1, 1, a - 1, b - 1));
	}
	return 0;
}

세그먼트 트리를 이용해 기초 문제를 풀어보았다. 세그먼트 트리를 응용하거나 다른 알고리즘과 함께 풀 수 있는 문제는 BOJ 에 많이 등록되어 있으니 관심 있다면 많이 풀어보는 것이 세그먼트 트리 이해에 도움이 될 것이다.

 

다른 세그먼트 트리 문제의 풀이는 #segment-tree 에서 확인할 수 있다.

https://readytojoin.tistory.com/tag/segment-tree

공작소