세그먼트 트리(Segment Tree, 구간트리)

 

여기, 여기, 여기, 여기 참조

특히 여기가 좋다.

완전이진트리 형태의 자료구조를 이용해서, element update가 존재하는 배열에 대해 특정 구간의 합, 곱, 최대값, 최소값 등을 효율적으로 구하는 자료구조

힙(heap)도 완전 이진트리를 이용하기 때문에 유사성이 있다고 볼 수 있다.

중간 중간에 element update가 존재하지 않는 경우, 세그먼트 트리까지는 필요없고 prefix sum등 간단한 테크닉을 쓰면 된다.

arr[12] = {3, 5, 6, 7, 2, 9, 4, 5, 2, 8, 1, 5} 이러한 배열이 있다고 하자.

완전이진트리 형태로 만들것이므로 $2^k >= 12$인 최소 k를 구해야한다. 

int k = (int)ceil(log2(n));
int tree_size = (1 << (k+1));  // base1 인덱스를 사용하기 때문에 +1을 해준다.