[C++] 세그먼트 트리 배열 크기

개요

저는 세그먼트 트리의 배열 크기를 결정할 때, 포화 이진트리로 생각하고 정합니다.

실제 세그먼트 트리는 완전 이진트리이지만, Out Of Bounds를 방지하기 위해서는 더미 배열이 필요하기 때문입니다.

 

만약에 노드 수가 2의 거듭제곱이라면 {노드 수 * 2 - 1} 만큼 배열이 필요합니다.

이유는 자식(노드 수) + 부모 노드(노드 수 - 1) 이기 때문입니다.

 

하. 지. 만. 노드의 수가 2의 거듭제곱이 아니라면, 세그먼트 트리는 보통 노드 수보다 넉~~넉히 약 4배 정도의 공간을 필요로 합니다.

더미 배열을 위한 2의 거듭제곱을 맞추는 과정에서 최대 2배만큼 늘어날 수 있기 때문입니다.

아래 예시를 보시면 이해가 될 것입니다.

예시

예를 들어, 배열의 크기가 10,000이라고 가정해 봅시다.

 

1. 10,000보다 크면서 가장 가까운 2의 거듭을 찾는다
   • 2^14 = 16,384
2. 이 값에 2를 곱한다.
   • 16,384 * 2 = 32,768
3. 세그먼트 트리의 최대 크기는 32,768

코드

int TREE_SIZE = 1;
const int N = 10000;

// 노드 수 보다 크면서 가장 작은 2의 거듭제곱 찾기
while (TREE_SIZE < N)
    TREE_SIZE <<= 1;

// 찾은 값의 2배
TREE_SIZE *= 2;

// 동적 할당
vector<int> seg;
seg.assign(TREE_SIZE, 0);