어떤 배열의 특정구간의 원소들의 합을 구한다고 해보자. 가장 직관적인 방법은 선형적으로 구하는 것이다. 이 선형적인 $O(N)$의 시간복잡도를 갖는다.
Segment Tree를 이용하게 되면 이를 $O(\log N)$안에 해결할 수 있다.
자식 노드들의 합을 더한 값을 저장하는 구간 합 트리라는 것을 생성해야 한다. 이는 데이터의 범위를 반씩 분할하며 그 구간의 합들을 저장하도록 초기 설정을 하는 것이다.
배열로 구현한 Binary Tree가 있다고 하자.
Root의 Index를 1로 설정한 후 구간 합 트리를 만들 것이다. 0이 아닌 1로 시작하는 이유는 x2 를 했을때 왼쪽 자식 노드를 가리키게 하기 위해서이다.
Segment Tree를 작성하기 위한 재귀함수를 만든다. 재귀함수는 합을 구할 범위를 인수로 받는다. 즉, 시작 index, 끝 index, 그리고 Segment Tree의 현재 노드를 인수로 받는다. 시작과 끝으로 범위를 구하면 그 범위를 절반으로 나눈다. [start ~ mid]는 좌측 노드들의 합, [mid+1 ~ end]는 우측 노드들의 합이다. 이 범위 합을 재귀함수로 호출해서 받는다.
만약 마지막 child에 도달하면 start, end가 같은 값으로 함수에 들어온다. 합을 구할 자식 노드들이 없으므로 그 노드의 값을 리턴한다.
글로 설명이 더 어렵다. 소스코드를 보면 직관적으로 이해할 수 있다.
int init(int start, int end, int node) {
if (start == end) return seg[node] = a[start];
int mid = (start + end) / 2;
return seg[node] =
init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}
Segment Tree의 마지막 층에는 배열의 원소의 수 만큼 노드가 들어가야한다. 예를 들어 참고하는 배열의 크기가 13이라고 하자. Segment Tree의 마지막 층에 [0~0], [1~1], [2~2], ... , [12~12]의 구간합을 저장하는 노드들이 있어야 한다.