Segment Tree (세그먼트 트리)

Segment Tree (세그먼트 트리)

구간 쿼리와 구간 갱신을 O(log n) 시간에 처리하는 이진 트리 기반 자료구조로, 구간 합, 최솟값, 최댓값, GCD 등 결합 법칙을 만족하는 연산에 활용

목적: 빠른 구간 쿼리, 구간 갱신, 범위 연산

특징: 완전 이진 트리, O(log n) 쿼리/갱신, 메모리 O(4n), 결합 법칙 필요

구조: 리프=원소, 내부 노드=자식 노드 연산 결과, 루트=전체 범위

구축: Bottom-Up 또는 Top-Down 재귀, O(n)

점 갱신(Point Update): 리프 갱신 후 부모 노드들 재계산, O(log n)

구간 쿼리(Range Query): 쿼리 범위를 트리 노드로 분해하여 결과 결합, O(log n)

Lazy Propagation: 구간 갱신을 지연시켜 O(log n)에 처리, 필요 시 자식에 전파

시간 복잡도: 구축 O(n), 쿼리/점갱신 O(log n), 구간갱신 O(log n) with Lazy

공간 복잡도: O(4n) ≈ O(n)

장점: 빠른 구간 연산(O(log n)), 유연한 연산, 구간 갱신 지원

단점: 메모리 사용, 구현 복잡, 동적 범위 불가

적용사례: 구간 합/최솟값/최댓값, 구간 갱신, 히스토그램, 2D 쿼리

비교: Segment Tree(log/유연) vs Fenwick Tree(log/합만/간단) vs Sqrt Decomposition(√n)

연관: Fenwick Tree, Lazy Propagation, 구간 쿼리, 이진 트리