본문 바로가기
알고리즘/알고리즘 이론

세그먼트 트리(Segment tree)

Primitive 2020. 12. 19. 01:06
728x90
반응형

Goal

  • 세그먼트 트리를 구현할 수 있다.

세그먼트 트리(Segment tree)란?

각 노드가 구간을 표현하는 트리이다.

(구간 트리 라고도 한다.)

 

세그 먼트 트리의 기본 구조

1. 루트가 표현하는 구간 크기가 2^n 형태인 경우

값의 개수가 2^n 꼴이 아닐 경우 남는 구간을 의미없는 기본 값으로 채워 포화 이진 트리 형태로 표현

 

 

2. 루트 구간이 표현하는 구간 크기가 2^n이 아닌 경우

 

 

  • Root Node : 전체 구간을 표현한다.
  • Leaf Node : 크기가 1인 구간. 즉, 값 자체를 표현한다.
  • Internal Node : [a, b] 구간 정보를 표현한다.

 

기본 연산

  • Query(from, to) : 구간 합과 같이 특정 구간에 대한 질의 처리
  • Update(index, data) : 값 변경에 영향을 받는 구간 갱신

두 연산 모두 O(logN)의 시간 복잡도를 갖는다.

공간 복잡도 : O(2N) = O(N)

 

구현

구간이 표현하고자 하는 값이 무엇인지에 따라 노드 값이 구간 합, 구간 최소 등으로 달라질 수 있다.

 

구간 합 구현 코드

#include <iostream>
#include <vector>

using namespace std;

const int N = 12;
int arr[] = { 1, 9 ,3, 8, 4, 5, 5, 9, 10, 3, 4, 5 };
vector<int> tree;

int init(int start, int end, int node) // root node = 1
{
	if (start == end) // base case
		return tree[node] = arr[start];

	int mid = (start + end) / 2;

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

int query(int start, int end, int node, int left, int right)
{
	// 경계를 완전히 벗어난 경우
	if (end < left || right < start)
		return 0;

	// node가 표현하는 범위[start, end]가 array[left, right]에 포함되는 경우
	if (left <= start && end <= right)
		return tree[node];

	// 그렇지 않으면 양쪽 구간 나눠서 질의 처리
	int mid = (start + end) / 2;
	return query(start, mid, 2 * node, left, right) + query(mid + 1, end, 2 * node + 1, left, right);
}

int query(int left, int right) // 외부 호출 인터페이스
{
	// root node = 1, root node가 표현하는 범위 [start, end] = [0, N - 1]
	int node = 1, start = 0, end = N - 1;
	return query(start, end, node, left, right);
}

void update(int index, int newValue, int start, int end, int node)
{
	if (index < start || end < index)
		return;

	if (start == end)
	{
		tree[node] = newValue;
	}
	else
	{
		int mid = (start + end) / 2;
		
		if (index <= mid)
		{
			update(index, newValue, start, mid, 2 * node);
		}
		else
		{
			update(index, newValue, mid + 1, end, 2 * node + 1);
		}

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

void update(int index, int newValue) // 외부 호출 인터페이스
{
	int node = 1, start = 0, end = N - 1;
	update(index, newValue, start, end, node);
}

int main()
{
	tree.resize(N * 4);
	init(0, N - 1, 1);

	// [a,b] 구간 쿼리
	cout << "[0, 11] : " << query(0, 11) << endl;
	cout << "[3, 8] : " << query(3, 8) << endl;

	update(1, 12); // array[1] : 9 -> 12
	update(3, 1); // array[3] : 8 -> 1
	
	cout << "update이후\n";
	cout << "[0, 11] : " << query(0, 11) << endl;
	cout << "[3, 8] : " << query(3, 8) << endl;

	return 0;
}

 

구간 최소 쿼리(RMQ, Range Minimum Query) 구현 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = numeric_limits<int>::max();

const int N = 12;
int arr[] = { 1, 9 ,3, 8, 4, 5, 5, 9, 10, 3, 4, 5 };
vector<int> tree;

int init(int start, int end, int node) // root node = 1
{
	if (start == end) // base case
		return tree[node] = arr[start];

	int mid = (start + end) / 2;

	return tree[node] = min(init(start, mid, 2 * node), init(mid + 1, end, 2 * node + 1));
}

int query(int start, int end, int node, int left, int right)
{
	// 경계를 완전히 벗어난 경우
	if (end < left || right < start)
		return INF;

	// node가 표현하는 범위[start, end]가 array[left, right]에 포함되는 경우
	if (left <= start && end <= right)
		return tree[node];

	// 그렇지 않으면 양쪽 구간 나눠서 질의 처리
	int mid = (start + end) / 2;
	return min(
		query(start, mid, 2 * node, left, right), 
		query(mid + 1, end, 2 * node + 1, left, right)
		);
}

int query(int left, int right) // 외부 호출 인터페이스
{
	// root node = 1, root node가 표현하는 범위 [start, end] = [0, N - 1]
	int node = 1, start = 0, end = N - 1;
	return query(start, end, node, left, right);
}

void update(int index, int newValue, int start, int end, int node)
{
	if (index < start || end < index)
		return;

	if (start == end)
	{
		tree[node] = newValue;
	}
	else
	{
		int mid = (start + end) / 2;
		
		if (index <= mid)
		{
			update(index, newValue, start, mid, 2 * node);
		}
		else
		{
			update(index, newValue, mid + 1, end, 2 * node + 1);
		}

		tree[node] = min(tree[2 * node], tree[2 * node + 1]);
	}
}

void update(int index, int newValue) // 외부 호출 인터페이스
{
	int node = 1, start = 0, end = N - 1;
	update(index, newValue, start, end, node);
}

int main()
{
	tree.resize(N * 4);
	init(0, N - 1, 1);

	// [a,b] 구간 쿼리
	cout << "[0, 11] : " << query(0, 11) << endl;
	cout << "[3, 8] : " << query(3, 8) << endl;

	update(1, 12); // array[1] : 9 -> 12
	update(3, 1); // array[3] : 8 -> 1
	
	cout << "update이후\n";
	cout << "[0, 11] : " << query(0, 11) << endl;
	cout << "[3, 8] : " << query(3, 8) << endl;

	return 0;
}

 

1) 세그먼트 트리 공간 할당 및 초기화

N크기 배열을 구간 트리로 만들 때, 안전하게 공간(capacity)을 할당 하기 위해 2가지 방법이 사용될 수 있다. 

 

Capacity 설정 방법 2가지

  1. N보다 같거나 큰 수 중 가장 가까운 2의 거듭 제곱 수를 찾는다. 그 수에 2를 곱한다.
  2. N * 4를 한다.
    • 4N은 모든 필요로 하는 경우의 수보다 크다. 공간 낭비가 있지만 쉽게 구할 수 있다는 장점이 있다.

 

첫 번째 경우는 루트 구간이 2의 거듭 제곱 형태로 표현되며, 포화 이진 트리 형태로 나타난다.

이때 사용되지 않는 노드는 의미 없는 값으로 대체시킨다.

ex) 

int height = (int)ceil(log2(n));
int capacity = 1 << (height + 1);

 

두번 째 경우는 루트 구간이 2의 거듭 제곱 형태가 될 수도 있고 아닐 수도 있다.

표현 가능한 모든 공간을 표현하기 위해 넉넉하게 공간을 할당하는 경우이다.

 

ex) 위 구현 코드에서 트리 공간 할당 코드

const int N = 12;
vector<int> tree;

...

tree.resize(N * 4);

 

초기화 구현 코드

int init(int start, int end, int node) // root node = 1
{
	if (start == end) // base case
		return tree[node] = arr[start];

	int mid = (start + end) / 2;

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

 

 

return 부분 코드는 해당 구간이 어떤 값을 표현하는지에 따라 다르게 표현하면 된다.

  • 구간 합 : 두 구간의 합으로 표현 (위 코드가 구간합 코드이다.)
  • 구간 최소 : 두 구간의 최소 값으로 표현

 

2) Query

int query(int start, int end, int node, int left, int right)
{
	// 경계를 완전히 벗어난 경우
	if (end < left || right < start)
		return 0;

	// node가 표현하는 범위[start, end]가 array[left, right]에 포함되는 경우
	if (left <= start && end <= right)
		return tree[node];

	// 그렇지 않으면 양쪽 구간 나눠서 질의 처리
	int mid = (start + end) / 2;
	return query(start, mid, 2 * node, left, right) + query(mid + 1, end, 2 * node + 1, left, right);
}

int query(int left, int right) // 외부 호출 인터페이스
{
	// root node = 1, root node가 표현하는 범위 [start, end] = [0, N - 1]
	int node = 1, start = 0, end = N - 1;
	return query(start, end, node, left, right);
}

루트 인덱스 = 1

루트 노드 구간[0, N - 1]

현재 노드 구간[start, end]

쿼리 구간[left, right]

 

  • 현재 노드 구간이 query 구간에 완전히 포함 되지 않는 경우 : 기본 값 리턴
  • 현재 노드 구간이 query 구간에 완전히 포함 되는 경우 : 현재 노드가 표현하는 구간 값 리턴
  • 그렇지 않은 경우(현재 노드 구간 query 구간이 일부 포함되는 경우) : 하위 노드 query 호출

 

3. Update

void update(int index, int newValue, int start, int end, int node)
{
	if (index < start || end < index)
		return;

	if (start == end)
	{
		tree[node] = newValue;
	}
	else
	{
		int mid = (start + end) / 2;
		
		if (index <= mid)
		{
			update(index, newValue, start, mid, 2 * node);
		}
		else
		{
			update(index, newValue, mid + 1, end, 2 * node + 1);
		}

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

void update(int index, int newValue) // 외부 호출 인터페이스
{
	int node = 1, start = 0, end = N - 1;
	update(index, newValue, start, end, node);
}

 

  • index가 현재 노드 구간에 포함되지 않는 경우 : 업데이트 하지 않음
  • index에 해당하는 leaf 노드인 경우 : 값을 갱신
  • index에 해당하는 leaf 노드를 포함하는 구간의 내부 노드(internal node)인 경우
    • leaf 노드가 포함되는 subtree(left / right) 업데이트
    • 두 subtree의 값을 통해 현재 노드 값 갱신

 

References

Segment Tree - arkainoh 블로그

세그먼트 트리 - 백준 블로그

728x90
반응형

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

이분 탐색  (0) 2021.05.10
펜윅 트리(Fenwick Tree)  (0) 2020.12.19
Prefix sum  (0) 2020.12.10
KMP 알고리즘  (0) 2020.09.07
탐욕 알고리즘(greedy algorithm)  (0) 2020.07.31

'알고리즘/알고리즘 이론' Related Articles

티스토리툴바