[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree)

 

재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다.

 

2. 비재귀 세그먼트 트리 구현

 

항의 개수가 N개라면 리프노드는 N번 노드부터 2N - 1번 노드까지 입니다. 이후 N번 노드부터 1번 노드까지 for문을 통해 돌면서 해당 노드의 왼쪽 노드는 i << 1, 오른쪽 노드는 i << 1 | 1로 표현됩니다.

 

따라서, 합을 구하려면 segTree[node] = segTree[ node << 1 ] + segTree[ node << 1 | 1 ] 로 표현해줍니다.

 

3. 비재귀 세그먼트 트리 구간합 구하기

구간에서 왼쪽 경계의 노드 번호가 짝수라면 부모 노드가 반드시 구간에 포함되고, 홀수라면 부모 노드가 구간에 절대 포함되지 않습니다. 부모 노드가 구간에 절대 포함되지 않을 때 왼쪽 경계의 값에 1을 더해줍니다.

 

구간에서 오른쪽 경계의 노드 번호가 짝수라면 부모 노드가 구간에 절대 포함되지 않고, 홀수라면 부모 노드가 반드시 구간에 포함됩니다. 부모 노드가 구간에 절대 포함되지 않을 때 오른쪽 경계의 값에 1을 빼줍니다.

 

이를 왼쪽 경계의 값과 오른쪽 경계의 값이 교차될 때까지 수행하고, 교차된다면 반복문을 탈출해줍니다.