세그먼트 트리 (Segment Tree)

세그먼트 트리 (Segment Tree)

배열의 구간 쿼리(범위 합·최소·최대 등)와 원소 갱신을 모두 O(log n) 시간에 처리하는 완전 이진 트리 기반 자료구조

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

특징: 완전 이진 트리, 각 노드는 구간 정보, 재귀적 구조, O(log n) 쿼리·갱신

구조: 리프 = 배열 원소, 내부 노드 = 자식 구간의 합계(또는 최소/최대)

연산

• •build(arr): 배열로부터 세그먼트 트리 구축, O(n)
• •query(L, R): 구간 [L, R]의 합계(또는 최소/최대), O(log n)
• •update(idx, val): 인덱스 idx를 val로 갱신, O(log n)

배열 크기: 4n (안전한 상한)

시간 복잡도: 구축 O(n), 쿼리·갱신 O(log n)

공간 복잡도: O(n)

장점: 빠른 구간 쿼리(O(log n)), 빠른 갱신(O(log n)), 다양한 연산(합·최소·최대·GCD)

단점: 구현 복잡도, 메모리 사용(4n), 정적 범위(배열 크기 고정)

적용사례: 구간 합·최소·최대, 동적 배열 쿼리, 좌표 압축, 2D 범위 쿼리

변형: Lazy Propagation(구간 갱신), 2D 세그먼트 트리

비교: 세그먼트 트리(쿼리·갱신 O(log n)) vs 누적합(쿼리 O(1)/갱신 O(n)) vs Fenwick(더 단순/메모리 적음)

연관: Fenwick 트리, 구간 쿼리, 범위 합, Lazy Propagation