[Range Queries] Segment Tree | C++

#include <iostream>
#include <vector>
using namespace std;

#define NUMBER 12

int tree[4 * NUMBER]; // 4를 곱하면 모든 범위를 커버할 수 있다. 개수에대하여 2의 제곱 형태의 길이를 가지기 때문...이라는데 머지?

int A[] = { 1,9,3,8,4,5,5,9,10,3,4,5 };
// 구간 합을 구하고자 하는 리스트를 저장한다.

void build(int node, int start, int end) {
	if (start == end) {
		tree[node] = A[start];
	}
	else {
		int mid = (start + end) / 2;
		// 재귀로 두 부분으로 나눈 뒤에 그 합을 자기 자신의 합으로 한다.
		// 처음 시작은 build(!,0,n-1)을 호출하여 재귀를 시작한다.
		build(2 * node, start, mid); //left child
		build(2 * node + 1, mid + 1, end); // right child
		
		tree[node] = min(tree[2 * node], tree[2 * node + 1]); // 더 작은 value를  저장한다.
	}
}
// 이미 모든 노드가 매 구간의 합을 가지고 있는 형태로 저장된다.
/*
* 데이터 개수가 N개일 때 N보다 큰 가장 가까운 N의 제곱수를 구한 뒤 그것의 2배까지 미리 배열의 크기를 만들어 두어야 한다.
* ex ) 데이터의 개수가 12개일 때 : 4**2 == 16 -> 16 x 2=32 32개의 index를 미리 만들어 두어야 세그먼트 트리 구현이 가능한다.
*/

int query(int node, int start, int end, int l, int r) {
	/*
	* start : 시작 인덱스
	* end : 끝 인덱스
	* left, right : 구간합을 구하고자 하는 범위
	*/
	
	// 범위 밖에 있는 경우
	if (r < start or end < 1) return 0;
	
	//범위 안에 있는 경우
	if (l <= start and end <= r) return tree[node];
	
	//아니면 분할하여 다시 탐색
	int mid = (start + end) / 2;
	int p1 = query(2 * node, start, mid, l, r);
	int p2 = query(2 * node+1, mid+1, end, l, r);
	return (p1 + p2);

}

void update(int node, int start, int end, int idx, int val) {
	// 리컬시브하게 동작하여 원하는 인덱스에 접근했을 경우 해당 index의 value값을 변경한다.
	if (start == end) {
		A[idx] += val;
		tree[node] += val;
	}
	else {
		int mid = (start + end) / 2;
		if (start <= idx and idx <= mid) {
			update(2 * node, start, mid, idx, val);
		}
		else {
			update(2 * node + 1, mid + 1, end, idx, val);
		}
		tree[node] = tree[2 * node] + tree[2 * node + 1];
	}
}
int main(void) {

}

 

 

 

이쁜거라도 봐야지...