10. 트리

세그먼트 트리 :

인덱스 구간의 합을 노드에 저장.

리프 노드에는 각 데이터가 저장되어 있음.

#include <stdio.h>
#define NUM_DATA 5
#define MAX_TREE (1<<4)
int segment_tree[MAX_TREE];
int arr[NUM_DATA + 1] = { 0, 10,20,30,40,50 };	//0번 index 공간 무시
void segment_update(int cur_node, int s, int e, int idx, int data) {
	if (s == e) {
		segment_tree[cur_node] = data;
		return 0;
	}
	int m = (s + e) / 2;
	//idx가 m보다 작으면 왼쪽 아니면 오른쪽
	if (idx <= m) segment_update(cur_node * 2, s, m, idx, data);
	else segment_update(cur_node * 2 + 1, m + 1, e, idx, data);
	segment_tree[cur_node] = segment_tree[cur_node * 2] + segment_tree[cur_node * 2 + 1];
}
int query(int cur_node, int s, int e, int q_s, int q_e) {
	if (q_s <= s && e <= q_e) return segment_tree[cur_node];
	if (e < q_s || q_e < s)return 0;
	int m = (s + e) / 2;
	int left_segment = query(cur_node * 2, s, m, q_s, q_e);
	int right_segment = query(cur_node * 2 + 1, m + 1, e, q_s, q_e);
	return left_segment + right_segment;
}

int main(void)
{
	int i;
	for (i = 1; i <= NUM_DATA; i++)
	{
		segment_update(1, 1, NUM_DATA, i, arr[i]);
	}
	printf("Query[1~5] : result = %d\n", query(1, 1, NUM_DATA, 1, 5));
}