알고리즘 [트리] - 세그먼트 트리

유의선·2023년 10월 15일

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

세그먼트 트리의 핵심 이론

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

1. 트리 초기화하기

리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다. 트리 배열의 크기를 구하는 방법은 $2^{k}$ ≥ N을 만족하는 k의 최솟값을 구한 후 $2^{k}$ * 2를 트리 배열의 크기로 정의하면 된다.

예를 들어 다음과 같은 샘플 데이터가 있다면 N = 8이므로 $2^{3}$ ≥ 8이므로 배열의 크기를 $2^{3}$ * 2 = 16으로 정의한다

샘플 데이터

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

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

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

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

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

2. 질의값 구하기

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

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

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

질의에서의 시작 인덱스와 종료 인덱스에 관해 부모 노드로 이동하면서 주어진 질의에 해당하는 값을 다음과 같이 구한다.

질의값 구하는 과정

start_index % 2 == 1일 때 해당 노드를 선택한다.
end_index % 2 == 0일 때 해당 노드를 선택한다.
1 에서 노드를 선택했다면 start_index = (start_index + 1) / 2 연산을 실행한다.
선택하지 않았다면 start_index = start_index / 2 연산을 실행한다.
2 에서 노드를 선택했다면 end_index = (end_index - 1) / 2 연산을 실행한다.
선택하지 않았다면 end_index = end_index / 2 연산을 실행한다.
1 ~ 4 를 반복하다가 end_index < start_index가 되면 종료한다.

1 ~ 2 에서 해당 노드를 선택했다는 것은 해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어가기 때문에 해당 노드를 질의값에 영향을 미치는 독립 노드로 선택하고, 해당 노드의 부모 노드는 대상 범위에서 제외한다는 뜻이다. 부모 노드를 대상 범위에서 제거하는 방법은 방법 3 ~ 4 에서 질의 범위에 해당하는 부모 노드로 이동하기 위해 인덱스 연산을 index / 2 가 아닌 (index + 1) / 2, (index - 1) / 2 로 수행하는 것이다.

질의에 해당하는 노드를 선택하는 방법은 구간 합, 최댓값 구하기, 최솟값 구하기 모두 동일하며 선택된 노드들에 관해 마지막에 연산하는 방식만 다르다.

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

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

다음은 구간 합 샘플을 이용해 2 ~ 6 번째 구간 합을 구하는 예제이다.

end_index < start_index가 되었으므로 종료하고 값을 구한다. 구간 합은 선택된 노드들의 합인 8 + 7 + 9 = 24가 된다.

3. 데이터 업데이트하기

업데이트 방식은 자신의 부모 노드로 이동하면서 업데이트한다는 것은 동일하지만, 어떤 값으로 업데이트할 것인지에 관해서는 트리 타입별로 조금 다르다.

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

구간 합에서는 원래 데이터와 변경 데이터의 차이만큼 부모 노드로 올라가면서 변경한다.
최댓값 찾기에서는 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 큰 값으로 업데이트한다. 업데이트가 일어나지 않으면 종료한다.
최솟값 찾기에서는 변경 데이터와 지신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 작은 값으로 업데이트한다. 업데이트가 일어나지 않으면 종료한다.