Segment Tree

---

개요

Segment Tree(세그먼트 트리)는 배열 또는 수열에서 **특정 구간에 대한 질의(Query)와 갱신(Update)**를 효율적으로 수행하기 위한 이진 트리 기반의 고급 자료구조입니다. 구간 합, 최소값/최대값, 최빈값, 최대공약수(GCD) 등 다양한 집계 연산을 O(log n) 시간 내에 처리할 수 있어, 알고리즘 문제, 게임 서버, 실시간 분석 시스템 등에서 널리 사용됩니다.

---

1. 개념 및 정의

Segment Tree는 크기 n의 배열에 대해 다음과 같은 연산을 빠르게 수행할 수 있는 트리입니다:

• build(): 배열을 기반으로 트리 구성 (O(n))
• query(l, r): 구간 [l, r]에 대한 집계 결과 반환 (O(log n))
• update(i, v): i번째 요소를 v로 갱신 (O(log n))

트리의 각 노드는 특정 구간을 대표하고, 리프는 원소 하나, 부모는 자식 구간의 결합 결과를 저장합니다.

---

2. 구조 및 동작 원리

노드 종류	의미	예시 구간 (0-based index)
리프 노드	배열의 개별 원소	[0,0], [1,1], ..., [n-1,n-1]
내부 노드	자식 노드 구간의 결과 저장	[0,1], [2,3], ..., [0,n-1]
루트 노드	전체 구간의 집계 결과	[0,n-1]

트리 높이는 O(log n)이며, 전체 트리 크기는 약 4n의 메모리를 사용합니다.

---

3. 시간 복잡도 비교

연산	일반 배열	Prefix Sum	Segment Tree
점 업데이트	O(1)	O(n)	O(log n)
구간 합 질의	O(n)	O(1)	O(log n)
구간 최소/최대	O(n)	불가능	O(log n)
구간 내 조건 탐색	O(n)	불가능	O(log n) + 조건 탐색

Prefix Sum은 정적 배열에만 적합한 반면, Segment Tree는 동적 업데이트가 가능합니다.

---

4. 활용 사례

분야	활용 예시	효과
온라인 게임 서버	HP 누적 회복량, 유닛 공격 범위 계산	실시간 구간 질의 가능
알고리즘 경진대회	Range Minimum Query(RMQ), 구간합 문제	빠른 풀이 구현 가능
금융 데이터 분석	시계열 데이터의 특정 기간 평균/최대값 계산	집계 연산 효율화
IoT 센서 데이터 처리	센서 범위 내 이상치 탐지	구간 기반 조건 탐색 최적화

실시간/부분 범위 연산이 필요한 문제에서 Segment Tree는 필수 자료구조입니다.

---

5. 확장형 구조

변형	설명	적용 상황
Lazy Propagation	구간 갱신 시 지연 계산 적용	구간 단위 업데이트 빈번할 때
Persistent Segment Tree	과거 버전을 유지하며 질의 가능	시계열 스냅샷, 히스토리 추적
Merge Sort Tree	다중 기준 집계 및 정렬 응답 처리	K번째 수 질의 등
Dynamic Segment Tree	크기가 매우 큰 배열 지원	희소 배열 처리에 최적화

문제 유형에 따라 적절한 세그먼트 트리 확장이 중요합니다.

---

6. 단점 및 고려사항

항목	설명	영향
구현 복잡성	재귀적 구조와 조건 처리 필요	버그 발생 시 디버깅 어려움
공간 사용량	배열 크기의 약 4배 필요	메모리 제약 시스템에 부담 가능
고정된 연산 유형	트리 설계 시 연산 종류 결정	유연성 낮음 (단, 확장 구조로 보완 가능)

적용 전에 목표 연산이 구간 집계인지 판단하는 것이 핵심입니다.

---

7. 결론

Segment Tree는 효율적인 구간 집계와 점 갱신 처리를 가능하게 하는 고급 자료구조로, 다양한 문제 해결에서 핵심적인 역할을 합니다. 알고리즘 실무, 실시간 서버 처리, 데이터 분석 등에서 자주 등장하며, Lazy, Persistent 등 변형을 통한 확장성도 높습니다. 구현은 어렵지만, **O(log n)**의 성능과 유연한 구조는 충분한 학습 가치가 있습니다.