티스토리 뷰
목차
데이터베이스나 실시간 분석 시스템을 구축할 때, 우리는 종종 "특정 범위의 합을 구하라"는 요청과 "데이터의 값을 수정하라"는 요청을 동시에 받게 됩니다. 단순히 누적 합(Prefix Sum)을 사용하면 구간 합을 구하는 것은 $O(1)$로 매우 빠르지만, 데이터 하나가 수정될 때마다 누적 합 배열을 다시 계산해야 하므로 $O(N)$의 시간이 소요됩니다. 반면, 단순 배열 수정은 $O(1)$이지만 구간 합을 구할 때마다 $O(N)$이 걸립니다. 이러한 두 연산 사이의 딜레마를 완벽하게 해결하고, 수정과 조회를 모두 $O(\log N)$으로 처리하는 마법 같은 자료구조가 바로 세그먼트 트리(Segment Tree)입니다. 본 포스팅에서는 세그먼트 트리의 논리적 구조와 구현 원리를 2,500자 이상의 상세한 설명으로 파헤쳐 보겠습니다.
1. 세그먼트 트리의 정의와 이진 트리 구조의 특징
세그먼트 트리는 주어진 배열의 구간 정보(합, 최댓값, 최솟값 등)를 보관하기 위해 완전 이진 트리의 형태를 빌려온 자료구조입니다. 트리의 리프 노드(Leaf Node)들은 배열의 실제 값들을 저장하며, 그 부모 노드들은 자식 노드들의 합(또는 특정 연산 결과)을 저장합니다. 이러한 계층적 구조 덕분에 우리는 전체 데이터를 뒤지지 않고도, 로그 스케일의 높이만큼만 탐색하여 원하는 구간의 정보를 조합해낼 수 있습니다.
1-1. 트리의 크기와 초기화(Init) 과정
세그먼트 트리를 배열로 구현할 때, 필요한 메모리 공간은 보통 원본 배열 크기 $N$의 4배 정도로 설정합니다. 이는 $N$이 2의 거듭제곱이 아닐 경우를 대비한 넉넉한 수치입니다. 트리를 만드는 과정은 재귀적으로 이루어집니다. 범위를 절반으로 나누어 왼쪽 자식과 오른쪽 자식을 만들고, 두 자식의 합을 현재 노드에 저장하는 방식을 리프 노드에 도달할 때까지 반복합니다. 이 전처리 과정은 단 한 번 $O(N)$의 시간으로 완료됩니다.
2. 구간 합 조회(Query)의 매커니즘: 분할 정복의 활용
구간 $[L, R]$에 대한 합을 구할 때, 세그먼트 트리는 현재 노드가 담당하는 범위와 찾고자 하는 범위의 관계를 세 가지 경우로 나눕니다. 첫째, 탐색 범위가 찾고자 하는 구간과 전혀 겹치지 않는 경우(0 반환), 둘째, 탐색 범위가 찾고자 하는 구간에 완전히 포함되는 경우(현재 노드 값 반환), 셋째, 일부만 겹치는 경우입니다. 세 번째 상황에서는 범위를 다시 절반으로 나누어 자식 노드들로 탐색을 이어갑니다. 이 과정은 트리의 높이인 $O(\log N)$을 넘지 않으므로, 수억 개의 데이터에서도 찰나의 순간에 결과를 반환합니다.
3. 데이터 수정(Update)의 효율성: 리프부터 루트까지
배열의 특정 인덱스 값이 바뀌면, 해당 리프 노드부터 시작하여 그 부모, 부모의 부모를 타고 올라가며 루트 노드까지 경로상에 있는 모든 노드의 값을 갱신합니다. 이 역시 트리의 높이만큼만 연산이 발생하므로 $O(\log N)$의 복잡도를 가집니다. 누적 합 방식이 수정 시 $O(N)$이 걸렸던 것과 비교하면, 데이터가 빈번하게 변하는 동적인 환경에서 세그먼트 트리가 왜 표준으로 자리 잡았는지 알 수 있습니다.
3-1. 세그먼트 트리의 시간 복잡도 요약
- 트리 생성(Build): $O(N)$
- 구간 쿼리(Query): $O(\log N)$
- 값 수정(Update): $O(\log N)$
4. 실무적 가치와 세그먼트 트리의 확장
세그먼트 트리는 단순히 '합'에만 국한되지 않습니다. 구간 내의 최댓값, 최솟값, 최대 공약수(GCD), 심지어는 특정 조건을 만족하는 원소의 개수를 찾는 등 결합 법칙이 성립하는 모든 연산에 응용될 수 있습니다. 금융권의 실시간 시세 변동 분석, 대규모 센서 데이터의 통계 산출, 그리고 게임 엔진의 공간 분할 쿼리 등 고성능 데이터 처리가 필요한 모든 곳에 세그먼트 트리의 원리가 녹아 있습니다.
# 세그먼트 트리 구현 예시 (Python)
def init(node, start, end):
if start == end:
tree[node] = arr[start]
return tree[node]
mid = (start + end) // 2
tree[node] = init(node*2, start, mid) + init(node*2+1, mid+1, end)
return tree[node]
def query(node, start, end, left, right):
if left > end or right < start:
return 0
if left <= start and end <= right:
return tree[node]
mid = (start + end) // 2
return query(node*2, start, mid, left, right) + query(node*2+1, mid+1, end, left, right)
1. 본질: 배열의 구간 정보를 이진 트리 구조로 저장하여 탐색 효율을 극대화합니다.
2. 강점: 데이터 수정과 구간 조회 모두를 $O(\log N)$이라는 경이로운 속도로 처리합니다.
3. 용도: 데이터의 변경이 잦은 환경에서 구간 합, 최댓값, 최솟값 등을 실시간으로 구할 때 사용됩니다.