1. 세그먼트 트리

• 주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조의 형태가 바로 세그먼트 트리이다.

✅ 세그먼트 트리의 핵심 이론

• 세그먼트 트리의 종류는 구간 합, 최대 최소 구하기로 나눌 수 있고, 구현 단계는 트리 초기화하기, 질의값 구하기(구간 합 또는 최대 최소), 데이터 업데이트하기로 나눌 수 있습니다.

☑️ 1단계: 트리 초기화하기 - 리프노드에 원본 데이터 입력

• 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다. 트리 배열의 크기를 구하는 방법은 2ⁱ ≥ N을 만족하는 i의 최솟값을 구한 후 2ⁱ2를 트리 배열의 크기**로 정의하면 된다. 예를 들어 다음과 같은 샘플 데이터가 있다면 N=8이므로 2³ ≥ 8 이므로 배열의 크기를 2³*2=16으로 정의한다.

샘플 데이터

{5, 8, 4, 3, 7, 2, 1, 6}

• 리프 노드에 원본 데이터를 입력한다. 이때 리프 노드의 시작 위치를 트리 배열의 인덱스로 구해야 하는데, 구하는 방식은 2ⁱ를 시작 인덱스로 취하면 된다. 예를 들어 i의 값이 3이면 start index = 8이 된다.

• 리프 노드를 제외한 나머지 노드의 값을 채운다. (2ⁱ-1부터 1번 쪽으로 채운다.) 채워야 하는 인덱스가 N이라고 가정하면 자신의 자식 노드를 이용해 해당값을 채울 수 있다. 자식 노드의 인덱스는 이진 트리 형식이기 때문에 2N, 2N+1이 된다. 각 케이스별로 적절하게 계산한다.

• 샘플을 이용해 3개의 케이스와 관련된 세그먼트 트리를 구성해 보았다. 구성한 트리 배열을 실제 트리 모양으로 구조화하면 다음과 같이 표현할 수 있다.

• 이렇게 세그먼트 트리를 구성해 놓으면 그 이후 질의와 관련된 결괏값이나 데이터 업데이트 요구사항에 관해 좀 더 빠른 시간 복잡도 안에서 해결할 수 있게 된다.

☑️ 2단계: 질의 값 구하기

• 주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경한다. 기존 샘플을 기준으로 한 인덱스값과 세그먼트 트리 배열에서의 인덱스값이 다르기 때문에 인덱스를 변경해야 한다. 인덱스 변경 방법은 다음과 같다.

질의 인덱스를 세그먼트 트리 인덱스로 변경하는 방법