주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태를 세그먼트 트리라고 한다.
더 큰 범위는 인덱스 트리라고 불리는데, 코딩 테스트 영역에서는 큰 차이가 없다고 생각해도 된다.
세그먼트 트리의 종류는 구간 합, 최대·최소 구하기로 나눌 수 있고, 구현 단계는 트리 초기화하기, 질의값 구하기(구간 합 or 최대·최소), 데이터 업데이트하기로 나눌 수 있다.
리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다. 트리 배열의 크기를 구하는 방법은 $2^k$ ≥ N을 만족하는 k의 최솟값을 구한 후 $2^k * 2$를 트리 배열의 크기로 정의하면 된다.
예를 들어 다음과 같은 샘플 데이터가 있다면 N=8 이므로 $2^3$≥ 8이므로 배열의 크기를 $2^3*2$ = 16으로 정의한다.
<aside> 💡 샘플 데이터
{5, 8, 4, 3, 7, 2, 1, 6}
</aside>
리프 노드에 원본 데이터를 입력한다. 이때 리프 노드의 시작 위치를 트리 배열의 인덱스로 구해야 하는데, 구하는 방식은 $2^k$를 시작 인덱스로 취하면 된다.
예를 들어 K의 값이 3이면 start_index = 8이 된다.
리프 노드를 제외한 나머지 노드의 값을 채운다($2^k$-1부터 1번 쪽으로 채움). 채워야 하는 인덱스가 N이라고 가정하면 자신의 자식 노드를 이용해 해당 값을 채울 수 있다. 자식 노드의 인덱스는 이진 트리 형식이기 때문에 2N, 2N+1이 된다.
실제 트리 모양으로 구조화하면 다음과 같은 트리가 나온다.
이렇게 세그먼트 트리를 구성해 놓으면 그 이후 질의와 관련된 결괏값이나 데이터 업데이트 요구 사항에 관해 좀 더 빠른 시간 복잡도 안에서 해결할 수 있게 된다.
주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경한다. 기존 샘플을 기준으로 한 인덱스값과 세그먼트 트리 배열에서의 인덱스값이 다르기 때문에 인덱스를 변경해야 한다.
<aside> 💡 질의 인덱스를 세그먼트 트리 인덱스로 변경하는 방법
세그먼트 트리 index = 주어진 질의 index + $2^k$ - 1 // 샘플에서는 k = 3
</aside>