세그먼트 트리(인덱스 트리)

• 주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태

세그먼트 트리의 핵심 이론

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

1. 트리 초기화하기

1. 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다. 트리 배열의 크기를 구하는 방법은

을 만족하는 K의 최솟값을 구한 후

를 트리 배열의 크기로 정의하면 된다.

예를 들어, 샘플 데이터 가 {5, 8, 4, 3, 7, 2, 1, 6}이면 N=8이므로 K는 3이고 배열의 크기를

으로 정의한다.

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

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

구성한 트리 배열을 실제 트리 모양으로 구조화하면 다음과 같이 표현가능하다.

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

2. 질의값 구하기

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

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

세그먼트 트리 index = 주어진 질의 index + 2^K - 1 //샘플에서는 K=3

🌸 질의값 구하는 과정

1. start_index % 2 == 1일 때 해당 노드를 선택한다.
2. end_index % 2 == 0일 때 해당 노드를 선택한다.
3. start_index depth 변경 : start_index = (start_index + 1) / 2 연산을 실행한다. ⇒ 부모노드로 간다.
4. end_index depth 변경 : end_index = (end_index -1 ) / 2 연산을 실행한다. ⇒ 부모노드로 간다.
5. 1~4를 반복하다가 end_index < start_index가 되면 종료한다.

• 1~2에서 해당 노드를 선택했다는 것은 해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어가기 때문에 해당 노드를 질의값에 영향을 미치는 독립노드로 선택하고, 해당 노드의 부모 노드를 대상 범위에서 제외한다는 뜻이다.
• 부모 노드를 대상 범위에서 제거하는 방법은 바로 3~4에서 질의 범위에 해당하는 부모 노드로 이동하기 위해 인덱스 연산을 index / 2가 아닌 (index +1) / 2, (index - 1) /2로 수행하는 것이다.
• 질의에 해당하는 노드를 선택하는 방법은 구간 합, 최댓값 구하기, 최솟값 구하기 모두 동일하며 선택된 노드들에 관해 마지막에 연산하는 방식만 다르다.

🌸 질의에 해당하는 노드 선택 방법

• 구간 합 : 선택된 노드를 모두 더한다.
• 최댓값 구하기 : 선택된 노드 중 MAX값을 선택해 출력한다.
• 최솟값 구하기 : 선택된 노드 중 MIN값을 선택해 출력한다.

예제를 통해 2~6번째 구간 합을 구해보자.

end_index < start_index이므로 종료하고 값을 구한다. 2~6번 구간 합의 값은 선택된 노드의 합인 8 + 9 + 7 = 24가 된다.

3. 데이터 업데이트하기

• 업데이트 방식은 자신의 부모 노드로 이동하면서 업데이트한다는 것은 동일하지만, 어떤 값으로 업데이트할 것인지에 관해서는 트리 타입별로 조금 다르다.
• 구간 합에서는 원래 데이터와 변경 데이터의 차이만큼 부모 노드로 올라가면서 변경한다.
• 최댓값 찾기에서는 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 큰 값으로 업데이트한다.
• 최솟값 찾기에서는 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 작은 값으로 업데이트한다. 업데이트가 일어나지 않으면 종료한다.

다음은 5번 데이터의 값을 7에서 10으로 업데이트하는 예시이다. 5번 데이터의 인덱스를 리프 노드 인덱스로 변경하면 5 + 7 = 12이므로 12번 노드의 값이 업데이트 된다.

---

출처 - 하루코딩