[알고리즘] 세그먼트 트리 ( Segment Tree ) #2 구현

 

여기에서는 세그먼트 트리에 대한 구현에 대한 설명을 하겠습니다. 재귀적인 방법으로 구간 연산과 함께 트리를 구성(build tree) 하고 원하는 구간의 값을 쿼리(get data) 하는 구현 방법을 설명합니다.

 

Data Sample

다음과 같은 Data를 정의하고 Segment Tree 를 구성한 후, 일부 구간의 값을 가져오는 예입니다.

const int MAX = 1000;
const int N = 10;

// Segment Tree : Leaf is update with _data[]
int tree[MAX];

int _data[] = { 9, 11, 8, 3, 22, 12, 23, 45, 31, 36 };

#1 : build_tree : 트리 구성

leaf node 까지 도달한 경우 데이터를 할당하고, 그렇지 않은 경우 하위 구간을 양분(left, right) 하여 할당합니다. 할당후에 return 된 값은 현재 tree 위치의 값으로 연산값을 저장하고 다시 return 하여 root 에 도달하게 됩니다.

 

Function Parameter

//! p : 현재 tree 의 위치
//! s : 현재 data 구각의 시작 위치
//! e : 현재 data 구간의 마지막 위치
//! return : 현재 위치의 data
int build_tree(int p, int s, int e)

 

Implementation

연산 종류에 따라 Operation 은 달라져야 하며, 구간합(sum)으로 구성된 build_tree 함수를 참고하세요.

int build_tree(int p, int s, int e) {
	if (s >= e) { 	//! 재귀 종료 조건 : Leaf Node 도달
		tree[p] = _data[s];
		return tree[p]; //! Leaf Node
	}
    
	int mid = (s + e) / 2;               	      //! 중간위치
	int lval = build_tree(p * 2, s, mid); 	      //! Left
	int rval = build_tree(p * 2 + 1, mid + 1, e); //! Right

	//! Operation
	tree[p] = lval + rval; // Plus
	return tree[p];
}

 

#2 : get_data : 데이터 쿼리

 

Function Parameter

build tree 에 비해 입력 인수가 2개 추가(q_s, q_e) 가 필요합니다.

현재 tree 위치와 data 이 시작과 끝 위치가 필요하고, 연산 구간의 시작(q_s) 과 끝 위치(q_e) 가 필요합니다.

//! p : 현재 tree 의 위치
//! s : data 시작 위치
//! e : data 마지막 위치
//! q_s : 검색 구간 시작 위치
//! q_e : 검색 구간 마지막 위치
//! return : 현재 위치의 data
int get_data_sum(int p, int s, int e, int q_s, int q_e)

 

Details

만약 data[3]  부터 data[7] 까지의 구간합을 구하고 싶다면, 각 인수는 이렇게 구성됩니다.

※ 처음 시작은 전체 데이터(data[0:9]) 보다 구간(data[3:7]) 작거나 같을 것이다.

//! 처음 호출에서는 p:0, s:0, e:9, q_s:2, q_e:7
//! 내부 호출에서는 p, s, e 는 구간별로 다르게 구성되고,
//! q_s:2, q_e:7 은 계속 유지되어 구간 탐색을 재귀적으로 수행한다.
int result = get_data_sum(0, 0, 9, 3, 7);

 

 

data[3] ~ data[7] 의 구간 합(sum[3:7])을 찾아야 하고, sum[0:9] 의 전체가 아닌 부분이므로 아래 순서로 진행합니다.

• 검색은 sum[0:9] 에서 시작
• 구간 탐색이 필요한지 Case 별로 확인
• 구간 탐색이 필요하다면, 하위 구간을 양분하여 검색

 

Implementation

Function 내부에서는 검색 중에 다음과 같은 구간 검색 Case 들이 발생하게 되므로 재귀적으로 함께 구현해야 합니다.

 

영역을 벗어난 구간 (Out of range)

sum[3:7] 에서 data[8], data[9] 는 이 영역의 외부 영역이므로  sum[8:9] 는 검색할 필요가 없게 됩니다.

//! case 1 : out of range ==> q_s(3) ~ q_e(7) < s(8) ~ e(9)
//! q_e(7) < s(8) ==> return 0
if ((e < q_s) || (qe < s)) return 0;

 

완전히 포함된 구간 (Included fully)

sum[3:7] 에서 data[4:7] 는 완전히 포함되므로 sum[4:7] 을 그대로 사용할 수 있겠습니다.

※ 이 경우에는 data[3] + sum[4:7]  이 결과가 될 것입니다.

//! case 2 : included fully ==> q_s(3) ~ s(4) ~ e(7) == q_e(7)
//! q_s(3) < s(4) && e(7) == q_e(7) ==> 현재 position data(sum[4:7]) return
if ((q_s <= s) && (e <= q_e)) return sum[4:7];

 

부분적으로 포함된 구간 (Included partially)

sum[0:3] 에서 data[3] 을 찾는 경우, sum[2:3] 의 일부 구간이므로 하위 노드를 두 개의 영역으로 나누어 검색하게 됩니다.

 

1. 검색 구간을 양분하여 left, right 를 호출하면, left 인 "sum[0:1]", right 는 "sum[2:3]" 을 검색

2. sum[0:1] 은 data[3:7]의 영역이 아니므로 0 을 return

3. sum[2:3] 은 data[3:7] 의 부분 구간이므로 하위 노드를 다시 검색

//! case 3 : included partially
//! s(0) ~ e(3) --> mid(1)
int mid = (s + e) / 2;

//! lval(0) <== Out of range : s(0) ~ mid(1), q_s(3) ~ q_e(7)
int lval = get_data_sum(p * 2, s, mid, q_s, q_e);

//! rval(sum[2:3]) <== partially : mid+1(2) ~ e(3), q_s(3) ~ q_e(7)
int rval = get_data_sum(p * 2 + 1, mid + 1, e, q_s, q_e);

 

 

4. sum[2:3] 의 하위 노드는  Leaf Node 가 되고, 동일하게 부분 구간에 대한 검색으로 data[2] 와 data[3]

5. sum[2:2] 은 data[2] 를 의미하고, data[2] 는 data[3:7] 의 영역이 아니므로 0을 return

6. sum[3:3] 은 data[3] 을 의미하고, data[3] 은 data[3:7] 이 영역에 완전히 포함되므로 data[3] 을 return

//! case 3 : included partially
//! s(2) ~ e(3) --> mid(2)
int mid = (s + e) / 2;

//! lval(0) <== Out of range : s(2) ~ mid(2), q_s(3) ~ q_e(7)
int lval = get_data_sum(p * 2, s, mid, q_s, q_e);

//! rval(data[3]) <== fully : mid+1(3) ~ e(3), q_s(3) ~ q_e(7)
int rval = get_data_sum(p * 2 + 1, mid + 1, e, q_s, q_e);

 

7. 최종적으로 sum[0:3]  을 위해 양분하여 검색한 결과는 Merge(0 + data[3]) 한 값이 된다.

//! lval <== sum(0:1) 의 결과로 0 return
//! rval <== sum(2:3) 의 결과로 data[3] 이 return
now = lval + rval;

//! sum(0:3) 의 결과는 0 + data[3] 이 return
return now;

 

구간 검색에 대해 Case 별로 처리한 최종 완성된 get_data_sum 함수입니다.

int get_data_sum(int p, int s, int e, int q_s, int q_e) {
	int now = 0;

	//! case 1 : out of range
	if ((e < q_s) || (qe < s)) return now;

	//! case 2 : included fully
	if ((q_s <= s) && (e <= q_e)) return tree[p];

	//! case 3 : included partially
	int mid = (s + e) / 2;
	int lval = get_data_sum(p * 2, s, mid, q_s, q_e);
	int rval = get_data_sum(p * 2 + 1, mid + 1, e, q_s, q_e);

	now = lval + rval;
	return now;	
}

 

See Also

해결해야 하는 문제에 따라 기존 데이터의 일부분을 갱신(update) 하는 부분이 필요한데, 아래 글을 참고하세요.

[알고리즘] 세그먼트 트리 ( Segment Tree ) #3 Update

[알고리즘] 세그먼트 트리 ( Segment Tree ) #3 Update