세그먼트 트리란 무엇인가?
이번 글에서는 데이터 구조 중 하나인 세그먼트 트리(Segment Tree)에 대해 알아보겠습니다. 세그먼트 트리의 개념을 본격적으로 살펴보기 전에, 먼저 다음과 같은 문제 상황을 가정해 보겠습니다.
크기가 n인 배열 arr[0, …, n-1]이 주어졌을 때, 우리는 아래 두 가지 연산을 수행해야 합니다.
- 인덱스 l부터 r까지 구간의 원소 합을 구합니다. (단, 0 ≤ l ≤ r ≤ n-1)
- 배열의 특정 위치 i의 값을 새로운 값 x로 변경합니다. 즉, arr[i] = x를 수행하며, i는 0부터 n-1 사이의 값입니다.
왜 세그먼트 트리를 사용할까?
단순히 배열을 순회하며 합을 구한다면 각 질의(query)마다 O(n)의 시간이 걸립니다. 하지만 질의와 업데이트가 매우 자주 발생하는 상황에서는 이 방식이 비효율적입니다. 바로 이럴 때 세그먼트 트리가 강력한 해결책이 됩니다. 세그먼트 트리를 활용하면 구간 합 조회와 값 변경을 모두 O(log n) 시간 안에 처리할 수 있습니다.
세그먼트 트리의 구조
세그먼트 트리는 다음과 같은 방식으로 표현됩니다.
- 리프 노드(Leaf Node): 주어진 배열의 각 원소가 리프 노드에 해당합니다.
- 내부 노드(Internal Node): 자식 노드(리프)들을 병합한 결과를 저장합니다. 병합 방식은 문제에 따라 달라질 수 있으며, 여기서는 해당 노드 아래에 있는 리프들의 합(sum)을 의미합니다.
예시로 이해하기
예를 들어 배열 [1, 3, 5, 7, 9, 11]이 있다고 가정해 봅시다. 이 배열로 만든 세그먼트 트리는 다음과 같은 형태를 가집니다.
루트 노드에는 전체 배열의 합인 36이 저장되고, 각 내부 노드에는 해당 구간의 합이 저장됩니다. 예를 들어 인덱스 0~2 구간의 합은 9, 인덱스 3~5 구간의 합은 27이 됩니다. 이러한 구조 덕분에 특정 구간의 합을 구할 때 트리를 따라 내려가며 필요한 노드만 조합하면 되므로, O(log n)의 빠른 속도로 질의를 처리할 수 있습니다.
핵심 정리
- 세그먼트 트리는 구간 합 질의와 원소 값 갱신을 모두 O(log n)에 처리하는 효율적인 자료구조입니다.
- 트리 생성에는 O(n)의 시간이 소요되며, 필요한 공간 역시 약 4n 정도의 배열로 충분히 표현할 수 있습니다.
- 병합 연산은 합뿐만 아니라 최솟값, 최댓값, 최대 공약수 등 다양한 연산으로 확장할 수 있습니다.