#8 세그먼트 트리

세그먼트 트리

선형적으로 그냥 구간 합을 구하는 것은 비효율적이다.

트리 구조를 활용해 구간합을 구하는 과정은 O(logN)의 시간복잡도를 가진다.

 

구간합트리는 부모에서부터 왼쪽  자식과 오른쪽자식에게 절반을 나누어 주어서,

쭉쭉 내려가는 트리이다.

예를들어 맨위에 start Node 가 40이라면

0~20까진 leftChild   21~40은 rightChild 로 쪼개지고,

또 leftChild 에서의 leftChild가 0~10  , leftChild의 rightChild 가 10~20을 담당하게 된다.

이런식으로 차례로 내려가는 트리를 만든뒤(구간이 세세히쪼개짐) 구간에 해당하는 부분 노드를 더해나가면 된다.

 

코드예시

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define NUMBER 7


int a[] = { 7,1,9,5,6,4,1 };
int tree[4 * NUMBER]; 
//4를 곱하면 모든 범위를 커버할  수 있다.


//start:시작인덱스  , end:끝 인덱스
int init(int start, int end, int node) {
	if (start == end) return tree[node] = a[start];
	int mid = (start + end) / 2;
	//재귀적으로 두 부분을 나눈 뒤에 그 합을 자기 자신으로 한다.
	return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

// start: 시작 인덱스, end: 끝 인덱스
//left,right : 구간 합을 구하고자 하는 범위
int sum(int start, int end, int node, int left, int right) {

	if (left > end || right < start) return 0;
	//범위 밖에 있는경우
	if (left <= start && end <= right) return tree[node];
	//범위 안에 있는 경우
	int mid = (start + end) / 2;
	return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}//그렇지 않다면 두 부분으로 나누어 합을 구하기


//start : 시작 인덱스, end : 끝 인덱스
//index: 구간 합을 수정하고자 하는 노드
//dif : 수정할 값
void update(int start, int end, int node, int index, int dif) {
	if (index<start || index>end) return;
	//범위 밖에 있는 경우
	tree[node] += dif;
	//범위 안에있으면 내려가며 다른 원소도 갱신
	if (start == end) return;
	int mid = (start + end) / 2;
	update(start, mid, node * 2, index, dif);
	update(mid + 1, end, node * 2 + 1, index, dif);
}

//구간합 트리 이용
int main(void) {
	//구간 합 트리의 인덱스를 제외하고는 모두 인덱스 0부터 시작
	init(0, NUMBER - 1, 1);
	//구간 합 트리 생성
	printf("0부터 6까지의 구간합: %d\n", sum(0, NUMBER - 1, 1, 0, 6));
	//구간 합 구하기
	printf("인덱스 5의 원소를 +3만큼 수정\n");
	update(0, NUMBER - 1, 1, 5, 3);
	//구간 합 갱신하기
	printf("3부터 6까지의 구간합: %d\n", sum(0, NUMBER - 1, 1, 3, 6));
	system("pause");
}

 

결과값

0부터 6까지의 구간합: 33
인덱스 5의 원소를 +3만큼 수정
3부터 6까지의 구간합: 19