29. 세그먼트 트리 (Segment Tree)

핵심 인사이트 (3줄 요약)

본질: 세그먼트 트리(Segment Tree)는 배열의 구간 쿼리(범위 합, 최솟값, 최댓값, GCD)와 점 업데이트를 O(log n)에 처리하는 완전 이진 트리 자료구조다. 배열을 분할 정복으로 재귀 구성한다.

가치: 구간 합 쿼리를 단순 배열로 처리하면 O(n), 누적 합(Prefix Sum)으로는 O(1) 쿼리지만 O(n) 업데이트. 세그먼트 트리는 쿼리와 업데이트 모두 O(log n)으로 균형을 맞춘다. 업데이트가 빈번한 구간 쿼리 문제의 표준 해법이다.

판단 포인트: 세그먼트 트리 vs 펜윅 트리(BIT) — BIT는 구현이 간단하고 상수 인자가 작지만 구간 최솟값 등 특정 연산은 세그먼트 트리만 가능하다. 레이지 프로파게이션(Lazy Propagation)은 구간 업데이트가 필요할 때 세그먼트 트리에 추가하는 핵심 최적화다.

Ⅰ. 개요 및 필요성

┌──────────────────────────────────────────────────────────┐
│         세그먼트 트리 구조 (배열 합)                       │
├──────────────────────────────────────────────────────────┤
│  배열: [1, 3, 5, 7, 9, 11]                               │
│                                                           │
│              [36]       ← 전체 합 (인덱스 1)             │
│            /       \                                     │
│         [16]       [20]  ← 좌우 절반                     │
│        /    \     /    \                                  │
│      [4]   [12] [9]  [11] ← 쿼터                        │
│     /  \  /  \  /  \                                     │
│   [1] [3][5][7][9][11] ← 리프 노드 (원소)                │
│                                                           │
│  구간 합 [1..4]: 루트→[16]→[4]+[12] = 16 → O(log n)      │
└──────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 세그먼트 트리는 회사 조직도 합산이다. CEO(루트)는 전체 합을 알고, 부장(중간 노드)은 자기 팀 합을 알며, 직원(리프)은 자신의 값을 안다. 특정 팀 합을 알려면 최소한의 상사만 물어보면 된다.

Ⅱ. 아키텍처 및 핵심 원리

구현 (배열 기반)

class SegmentTree:
    def __init__(self, arr):
        n = len(arr)
        self.tree = [0] * (4 * n)
        self.build(arr, 0, n-1, 1)
    
    def build(self, arr, l, r, node):
        if l == r:
            self.tree[node] = arr[l]
            return
        mid = (l + r) // 2
        self.build(arr, l, mid, 2*node)
        self.build(arr, mid+1, r, 2*node+1)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
    
    def query(self, l, r, node, nl, nr):  # 구간 합 O(log n)
        if r < nl or nr < l: return 0
        if l <= nl and nr <= r: return self.tree[node]
        mid = (nl + nr) // 2
        return self.query(l, r, 2*node, nl, mid) +                self.query(l, r, 2*node+1, mid+1, nr)

레이지 프로파게이션 (Lazy Propagation)

문제: 구간 [l, r] 전체에 +k 업데이트 → 순진하게 하면 O(n)
해결: 업데이트를 지연(lazy) 저장 → 필요할 때만 전파
→ 구간 업데이트도 O(log n) 가능

📢 섹션 요약 비유: 레이지 프로파게이션은 일괄 업무 처리다. 100명 직원 급여를 일일이 바꾸는 대신, "팀 전체 +10% 인상" 메모만 남겨두고 실제 계산은 각 직원 급여를 조회할 때만 한다.

Ⅲ. 비교 및 연결

비교	배열	누적 합	세그먼트 트리	펜윅 트리
쿼리	O(n)	O(1)	O(log n)	O(log n)
업데이트	O(1)	O(n)	O(log n)	O(log n)
구현	쉬움	쉬움	복잡	간단
구간 최솟값	O(n)	❌	O(log n)	어려움

📢 섹션 요약 비유: 세그먼트 트리는 빠른 인터넷 뱅킹이다. 잔액 조회(쿼리)와 입금(업데이트) 모두 빠르게 처리할 수 있어, 조회만 빠른 장부(누적 합)나 입금만 빠른 장부(배열)보다 균형잡힌 성능이다.

Ⅳ. 실무 적용 및 기술사 판단

응용 문제

구간 최솟값 (Range Minimum Query):
  세그먼트 트리 리프 = 원소, 내부 = min(자식)
  → 구간 최솟값 O(log n), 업데이트 O(log n)

구간 최솟값 + Offline: 스파스 테이블 (O(1) 쿼리, O(n log n) 전처리)

구간 업데이트 + 구간 합: 레이지 프로파게이션 필수

지속 세그먼트 트리 (Persistent Segment Tree):
  시간축 버전 관리 → 과거 시점 쿼리 O(log n)
  → 오프라인 쿼리, K번째 원소 찾기

📢 섹션 요약 비유: 지속 세그먼트 트리는 시간 여행 가능한 데이터베이스다. 트리의 모든 과거 버전을 O(log n) 공간으로 유지해서 "3단계 전 상태의 구간 합이 얼마였나?"를 빠르게 조회할 수 있다.

Ⅴ. 기대효과 및 결론

기대효과	내용
균형 성능	쿼리·업데이트 모두 O(log n)
범용성	합·최소·최대·GCD 등 다양한 연산
확장성	레이지·지속 세그먼트 트리로 기능 확장

세그먼트 트리는 기술 면접과 경쟁 프로그래밍의 핵심 자료구조다. Java TreeMap, Python Sorted Containers, C++ segment_tree(custom) 등으로 구현하며, DB 인덱싱·범위 쿼리 최적화의 원리적 기반이 된다.

📢 섹션 요약 비유: 세그먼트 트리는 데이터베이스 B-트리의 알고리즘 버전이다. B-트리가 디스크 기반 범위 쿼리를 최적화하듯, 세그먼트 트리는 메모리 내 구간 쿼리를 최적화한다.

📌 관련 개념 맵

개념	연결 포인트
펜윅 트리 (BIT)	세그먼트 트리 간소화 버전
스파스 테이블	정적 구간 최솟값 O(1) 쿼리
레이지 프로파게이션	구간 업데이트 최적화
지속 세그먼트 트리	버전 관리·시간축 쿼리
분할 정복	세그먼트 트리의 설계 원리

📈 관련 키워드 및 발전 흐름도

[배열 선형 탐색 — 구간 쿼리 O(n)]
    │
    ▼
[누적 합 — 정적 구간 합 O(1) 쿼리]
    │
    ▼
[세그먼트 트리 — 동적 구간 쿼리·업데이트 O(log n)]
    │
    ▼
[레이지 프로파게이션 — 구간 업데이트 O(log n)]
    │
    ▼
[지속 세그먼트 트리 — 시간축 버전 관리]

👶 어린이를 위한 3줄 비유 설명

세그먼트 트리는 회사 조직도예요! CEO(루트)는 전체 합을 알고, 팀장은 팀 합을, 직원은 자기 값을 알아요.
구간 합·최솟값 조회와 값 업데이트를 모두 O(log n)으로 빠르게 처리할 수 있어요!
레이지 프로파게이션은 "팀 전체 급여 +10%" 메모만 남겨두고 나중에 계산하는 스마트 지연 업데이트예요!