세그먼트 트리(Segment Tree) 완벽 정리: 기본 개념부터 구간 합, 최솟값, Lazy Propagation까지

세그먼트 트리(Segment Tree) 완벽 정리: 기본 개념부터 구간 합, 최솟값, Lazy Propagation까지

**세그먼트 트리(Segment Tree)**는 배열의 구간 정보를 효율적으로 저장하고, 빠르게 질의/갱신할 수 있는 자료구조입니다.
특히 구간 합, 최댓값, 최솟값, 특정 조건 카운트 등에서 **O(log N)**의 시간복잡도를 제공하여,
코딩 테스트, 실전 알고리즘 문제에서 매우 중요한 역할을 합니다.

이번 글에서는 세그먼트 트리의 구조, 구축(Build), 쿼리(Query), 업데이트(Update) 방법과
**Lazy Propagation(지연 업데이트)**까지 단계별로 정리합니다.

---

✅ 세그먼트 트리란?

원래 배열을 트리 형태로 분할하여 저장하는 구조
각 노드는 특정 구간을 대표하고, 구간 전체에 대한 정보를 저장함

🔹 주요 기능

• 특정 구간의 합/최댓값/최솟값을 빠르게 구하기
• 특정 원소 또는 구간 값을 빠르게 업데이트

⏱ 시간복잡도

• 트리 구축: O(N)
• 쿼리/업데이트: O(log N)

---

🧱 트리 구조 예시

배열 A = [5, 8, 6, 3, 2, 7, 2, 6]

세그먼트 트리는 다음과 같이 구간을 분할해 저장:

             [0~7]
          /         \
      [0~3]         [4~7]
     /     \        /     \
  [0~1]  [2~3]   [4~5]  [6~7]
  /   \   /  \    /  \    /  \
[0] [1][2][3]  [4][5]  [6][7]

각 노드에는 해당 구간의 합 또는 최솟값 등의 정보가 저장됩니다.

---

✅ 기본 구현 (구간 합 기준)

반응형

class SegmentTree:
    def __init__(self, arr):
        self.N = len(arr)
        self.tree = [0] * (4 * self.N)
        self.build(arr, 0, 0, self.N - 1)

    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, node * 2 + 1, start, mid)
            self.build(arr, node * 2 + 2, mid + 1, end)
            self.tree[node] = self.tree[node * 2 + 1] + self.tree[node * 2 + 2]

    def query(self, l, r, node=0, start=0, end=None):
        if end is None:
            end = self.N - 1
        if r < start or end < l:
            return 0  # 구간 밖
        if l <= start and end <= r:
            return self.tree[node]  # 완전히 포함
        mid = (start + end) // 2
        left_sum = self.query(l, r, node * 2 + 1, start, mid)
        right_sum = self.query(l, r, node * 2 + 2, mid + 1, end)
        return left_sum + right_sum

    def update(self, index, value, node=0, start=0, end=None):
        if end is None:
            end = self.N - 1
        if start == end:
            self.tree[node] = value
        else:
            mid = (start + end) // 2
            if index <= mid:
                self.update(index, value, node * 2 + 1, start, mid)
            else:
                self.update(index, value, node * 2 + 2, mid + 1, end)
            self.tree[node] = self.tree[node * 2 + 1] + self.tree[node * 2 + 2]

---

📈 구간 합 쿼리 사용 예

arr = [5, 8, 6, 3, 2, 7, 2, 6]
st = SegmentTree(arr)

print(st.query(2, 5))  # 출력: 6+3+2+7 = 18

st.update(3, 10)  # arr[3] = 10
print(st.query(2, 5))  # 출력: 6+10+2+7 = 25

---

🔥 Lazy Propagation (지연 업데이트)

여러 원소를 한꺼번에 업데이트할 때, 쿼리 속도를 유지하기 위한 최적화 기법
→ 구간 업데이트에도 O(log N) 보장

기본 아이디어

• 업데이트 정보를 바로 반영하지 않고, 필요할 때만 적용 (지연)
• lazy 배열을 사용하여 변경 예정 값을 저장

Lazy Propagation은 다음 글에서 별도 실습과 함께 자세히 설명 예정입니다.

---

🎯 세그먼트 트리로 해결 가능한 문제

문제 유형 설명

구간 합 구하기	특정 구간의 합을 빠르게 구함
구간 최솟값, 최댓값	RMQ, RMX 문제에 활용
구간 카운팅	홀수/짝수 개수, 조건 만족 개수 등
구간 갱신	특정 범위 값을 일괄 변경 (Lazy)
LCA 변형 문제	오일러 투어 + RMQ로 LCA 구현 가능

---

📘 백준 세그먼트 트리 문제 모음

번호 제목 유형

2042	구간 합 구하기	기본 세그먼트 트리
2357	최솟값과 최댓값	RMQ/RMX
12837	가계부	구간 업데이트
10999	구간 합 구하기 2	Lazy Propagation
16975	수열과 쿼리 21	구간 갱신 & 쿼리

---

📌 결론 및 요약

• 세그먼트 트리는 구간 연산을 빠르게 처리할 수 있는 트리 기반 자료구조입니다.
• 트리 구축: O(N), 쿼리/업데이트: O(log N)
• Lazy Propagation으로 구간 업데이트도 효율적 처리 가능
• 실전 알고리즘 문제에서 자주 출제되는 고난이도 테크닉이므로 꼭 숙지!

👉 다음 글에서는 Lazy Propagation의 원리와 실제 구현 코드를 기반으로
구간 업데이트 + 구간 질의 문제를 풀어봅니다.

---

📚 참고자료 및 출처

• 『알고리즘 문제 해결 전략』 (구종만 저)
• 백준 2042, 2357, 10999
• CP-Algorithms – Segment Tree

---

 

세그먼트트리, segment tree, 구간합, 최솟값, 파이썬 알고리즘, 코딩테스트 자료구조, 구간 질의, lazy propagation, 트리 자료구조, SEO 최적화 10개