구간 트리(Segment Tree)

구간 트리(segment tree)는 이미 존재하는 자료들(정렬되지 않음)을 전 처리한 후, 특정 구간에 대한 질의(query)를 효율적으로 답하는 자료구조이다. 물론 작성하려는 부분은 컴퓨터 공학에서 다루는 구간 트리 와는 구현 방식을 비슷하지만 엄밀히 따지면 다른 자료구조로 그저 알고리즘 대회에서 사용되는 구간 트리를 다룰 것이다.

 

특정 구간에 대한 질의는 그 형식이 다양하다. 예를 들어 특정 구간에 대한 합이 될 수도 있고, 특정 구간에 대한 최솟값 혹은 최댓값이 될 수도 있다. 이를 배열에서 구현하게 되면 특정 구간을 순회하면서 답을 내야 하기 때문에 질문 하나에 대해 O(N)의 시간이 걸리게 된다.

 

구간 트리는 이진트리로 구현하며, 루트 노드는 모든 구간 [0, n-1]을 의미하고 left는 [0~(n-1)/2], right는 [(n-1)/2+1, n-1]을 표현한다. 그리고 그 아래 노드들도 부모 노드가 의미하는 구간을 반씩 나눠가면서 처리하게 되고, 가장 마지막에 존재하는 노드(leaf)들은 길이가 1인 구간을 의미하게 된다.

 

이렇게 전처리해서 만들어지는 구간 트리는 어떤 구간에 대한 질의가 들어오던, 구간 트리 노드에 포함된 구간들의 합집합으로 표현할 수 있게 된다.

 

이제 특정 구간에 대해 최댓값을 반환하는 구간 트리를 구현해보자.

 

구간 트리는 굉장히 균형 잡힌 이진트리라고 할 수 있다. 이를 배열로 표현해보자.

루트 노드를 배열의 1번 인덱스로 잡고, 노드 i의 left와 right는 각각 2*i, 2*i+1번 인덱스로 잡아주면 구간 트리에 들어갈 정보를 일차원 배열로 표현할 수 있게 된다.

 

문제는 배열의 크기이다. 맨 처음에 잡게 되는 배열 크기는 얼마로 해야 적당할까?

입력으로 들어오는 원소들의 총개수를 N이라고 하자. 배열의 크기는 만들어지는 리프 노드들의 인덱스 번호의 최댓값이 얼마냐에 따라 달라진다. 예를 들어 N = 10인 경우 리프 노드들 중, 인덱스 번호가 가장 큰 인덱스 번호는 25번이 된다. 따라서 배열의 크기는 26이 되어야 한다.

 

N이 2의 거듭제곱인 경우에는 배열의 크기를 2*N으로 잡아주면 된다. 하지만 N이 2의 거듭제곱이 아닌 경우 배열의 크기를 안전하게 구하려면, 가장 가까운 2의 거듭제곱으로 N을 올림 한 뒤, 2를 곱해줘야 한다. 거듭제곱인 경우보다 거듭제곱이 아닌 경우가 더 많기 때문에 매번 위와 같은 처리를 하기 귀찮다. 따라서 메모리를 좀 낭비하더라도 배열의 크기를 4*N으로 잡아주면 된다.

 

1. 전처리

우선 입력으로 들어오는 값들은 따로 vector(arr)에다가 저장해놓을 것이다. 트리도 마찬가지로 vector(tree) 배열로 구현할 예정이다. vector배열을 사용하는 이유는 배열의 크기를 런타임 내에 정해줄 수 있기 때문이다.

 

전처리시 루트 노드(인덱스 번호는 1)부터 시작하게 된다. 재귀로 구현할 것이기 때문에 루트 노드가 의미하는 구간(모든 구간)에 대한 최댓값이 바로 만들어지지 않는다. 전처리에 사용되는 init함수는 주어진 구간에 대한 최댓값을 반환하도록 한다. 따라서 init함수를 모든 노드에 대해 재귀적으로 실행하게 되면, 리프 노드까지 갔다가 한 단계씩 다시 돌아오면서 구간에 대한 최댓값을 tree vector배열에 저장하게 될 것이다.

int init(int node, int start, int end) {
	if(start == end) return tree[node] = arr[start];
	
	int leftNode = init(node*2, start, (start + end) / 2);
	int rightNode = init(node*2+1, (start + end) / 2 + 1, end);
	
	return tree[node] = max(leftNode, rightNode);
}

인자로 주어지는 node는 말 그대로 tree에서의 인덱스 번호이고, start와 end는 구간의 시작과 끝을 의미한다.

 

start와 end가 같다면, 리프 노드에 도달했다는 의미이므로 tree[node]에 arr[start]를 할당한 후 반환한다. 만약 같지 않다면 left와 right를 전처리한 후 반환되는 값을 비교해 더 큰 값을 tree[node]에 저장시키면 된다.

 

이 전처리 과정에서는 노드의 수와 같은 시간이 걸리기 때문에 시간 복잡도는O(N)이다.

 

2. 질의(query)

질의를 할 때는 현재 보고 있는 구간과 찾으려는 구간을 동시에 받아야 한다.

만약 현재 보고 있는 구간과 찾고자 하는 구간의 교집합이 공집합인 경우에는 의미 없는 값을 반환해야 한다.

찾으려는 구간(findStart ~ findEnd)에 현재 보고 있는 구간(left ~ right)이 완전히 포함되는 경우 전처리해둔 값을 반환하면 된다.

이외의 모든 경우는 left와 right에 대해 똑같이 query함수를 재귀 호출시키고 둘 중 더 큰 값을 반환하도록 하면 된다.

int query(int node, int start, int end, int findStart, int findEnd) {
	if(findEnd < start || end < findStart) return -1;
	if(findStart <= start && end <= findEnd) return tree[node];
	
	int leftNode = query(node*2, start, (start + end) / 2, findStart, findEnd);
	int rightNode = query(node*2+1, (start + end) / 2 + 1, end, findStart, findEnd);
	
	return max(leftNode, rightNode);
}

 

이제 query함수의 시간 복잡도에 대해 알아보자.

찾으려는 구간에 보고 있는 구간이 포함되거나, 아예 둘의 교집합이 공집합인 경우는 바로 종료하기 때문에 재귀 호출을 하면서 모든 노드를 탐색하지는 않는다. 찾으려는 구간이 보고있는 구간의 중간에 위치해서 left와 right 모두 query함수를 실행하는 경우는 두 번 이상 존재할 수가 없다. 동시에 여러 구간을 검색하지 않는 이상 구간은 계속 이어져 있기 때문이다.

 

따라서 트리의 높이와 가깝게 연산하기 때문에 시간 복잡도는 알 수 있다.

 

3. 변경(update)

변경을 하려면 먼저 변경하고픈 인덱스 번호와 어떤 값으로 바꿀지를 입력으로 받아야 한다.

트리를 내려갈 때는 인덱스 번호가 현재 보고 있는 범위에 포함되지 않는 경우, 그 범위에 해당하는 노드 값을 반환시킨다. 보고 있는 구간의 길이가 1인 경우, 인덱스 번호에 해당하는 리프 노드로 왔다는 뜻이므로 arr[index]와 함께 값을 바꿔준다. 그 외의 경우, left와 right에 대해서도 update를 호출하고 반환되는 값 중 더 큰 값으로 현재 보고 있는 노드 값에 할당한다.

int update(int node, int start, int end, int index, int value) {
	if(index < start || index > end) return tree[node];
	if(start == end) return tree[node] = arr[index] = value;
	
	int leftNode = update(node*2, start, (start + end) / 2, index, value);
	int rightNode = update(node*2 + 1, (start + end) / 2 + 1, end, index, value);
	return tree[node] = max(leftNode, rightNode);
}

 

update의 시간 복잡도는 목표로 잡는 구간이 인덱스 번호와 같기 때문에 left와 right 모두로 부터 update가 재귀호출되어 더 내려가는 경우는 존재하지 않는다. 즉, 트리의 높이와 같기 때문에 시간복잡도는 O(logN)이다.