세그먼트 트리는 구간에 대한 다양한 쿼리에 빠르게 답할 수 있게 해 주는 매우 강력하고 유연한 자료 구조입니다.
구체적인 문제를 살펴봅시다. $n$개의 정수로 이루어진 배열 $a$가 주어지고, 다음 두 가지 유형의 쿼리에 답해야 합니다.
- 한 셀의 값을 변경합니다(즉,
a[k] = x대입을 처리합니다). - $l$부터 $r$까지의 구간에 있는 원소 $a_i$의 합을 출력합니다.
두 쿼리 모두 $O(\log n)$ 시간에 처리해야 합니다.
세그먼트 트리의 구조
문제를 해결하기 위해 원래 배열에 다음과 같은 조작을 해 봅시다.
배열 전체의 합을 계산하여 어딘가에 기록해 둡시다. 그다음 배열을 반으로 나누고, 각 절반의 합을 계산하여 이것도 어딘가에 기록해 둡시다. 그다음 각 절반을 다시 반으로 나누고, 길이가 1인 구간에 이를 때까지 이 과정을 계속 반복합니다.
이 분할 과정은 트리 형태로 나타낼 수 있습니다.
이 트리의 루트는 구간 $[0, n)$에 대응하며, 각 노드(리프는 제외)는 정확히 두 개의 자식을 가지고, 이 자식들 역시 어떤 구간에 대응합니다. 여기에서 ‘세그먼트 트리’라는 이름이 유래했습니다.
여러 가지 유용한 성질
세그먼트 트리의 높이는 $\Theta(\log n)$입니다. 새로운 레벨로 내려갈 때마다 구간의 길이가 절반으로 줄어들기 때문입니다. 이 사실은 연산의 점근적 복잡도를 평가하는 데 핵심이 됩니다.
임의의 반구간은 트리의 정점에 대응하는 $O(\log n)$개의 서로 겹치지 않는 반구간으로 분할됩니다. 각 층에서 최대 두 개의 구간만 있으면 충분하기 때문입니다.
트리는 $2n$개 미만의 정점을 포함합니다. 세그먼트 트리의 첫 번째 레벨은 정점 하나(루트)를 포함하고, 두 번째 레벨은 최악의 경우 정점 두 개를 포함하며, 세 번째 레벨에는 최악의 경우 정점 네 개가 있고, 이런 식으로 정점의 수가 $n$에 도달할 때까지 계속됩니다. 따라서 최악의 경우 정점의 수는 합 $n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \ldots + 1 < 2n$으로 추정됩니다. 그러므로 메모리 사용량은 선형입니다.
2의 거듭제곱이 아닌 $n$의 경우, 세그먼트 트리의 모든 레벨이 완전히 채워지지는 않습니다. 예를 들어 $n=3$일 때 루트의 왼쪽 자식은 두 개의 자손을 가지는 구간 $[0, 2)$이지만, 루트의 오른쪽 자식은 리프인 구간 $[2, 3)$입니다.
좋습니다, 이것이 우리에게 어떻게 도움이 됩니까?
이러한 구조를 사용하여 원래 문제를 어떻게 해결하는지 설명하겠습니다.
갱신 쿼리. 정점에 저장된 값들이 새 값 $a[k] = x$에 맞도록 갱신해야 합니다.
$k$번째 원소가 합에 포함되는 모든 노드를 갱신합시다. 그러한 노드는 각 레벨마다 하나씩, 총 $\Theta(\log n)$개입니다.
이는 재귀 함수로 구현할 수 있습니다. 함수에는 세그먼트 트리의 현재 정점이 전달되고, 함수는 두 자식 중 하나(자신의 구간에 $k$번째 원소를 포함하는 자식)에 대해 재귀 호출을 수행한 다음, 세그먼트 트리를 구축할 때와 정확히 같은 방식으로 현재 정점의 합 값을 다시 계산합니다.
합 쿼리. 모든 정점에 올바른 값이 저장되어 있다는 것을 알고 있으므로, 이 값들을 이용하여 구간의 합을 계산해야 합니다.
이것도 재귀 함수로 만들어 봅시다. 다음 세 가지 경우를 살펴보겠습니다:
- 정점의 구간이 쿼리 구간에 완전히 포함되면, 그 정점에 기록된 합을 반환합니다.
- 정점의 구간과 쿼리 구간이 겹치지 않으면 0을 반환합니다.
- 그렇지 않으면 재귀적으로 두 절반으로 나누고, 두 자식에 대한 이 함수 값의 합을 반환합니다.
이것이 왜 $O(\log n)$에 동작하는지 이해하려면 “흥미로운” 구간, 즉 새로운 재귀 호출을 만들어 내는 구간의 개수를 추정해야 합니다. 그러한 구간은 쿼리의 경계를 포함하는 구간뿐이며, 나머지 구간은 곧바로 종료됩니다. 구간의 두 경계는 각각 $O(\log n)$개의 구간에 포함되므로, 최종 점근 복잡도 역시 이와 같습니다.
세그먼트 트리는 합 외에도 훨씬 더 많은 용도로 사용할 수 있습니다.
이 장의 나머지 부분에서는 이 구조의 다양한 구현과 변형, 그리고 그 응용을 살펴보겠습니다.