[Python] 알고리즘 개념15 - 세그먼트 트리(Segment Tree)

 

 

🚀 1. 세그먼트 트리란?

세그먼트 트리(Segment Tree)는 배열의 특정 구간에 대한 쿼리(합, 최소값, 최대값 등)를 빠르게 처리하는 트리 형태의 자료구조예요.

 

💡 왜 세그먼트 트리가 필요할까요?

• 만약 배열의 특정 범위의 합을 여러 번 구해야 한다면, 단순한 반복문(O(n))으로는 시간이 오래 걸려요.
• 세그먼트 트리는 한 번 구성하면(O(n)), 이후 모든 쿼리를 O(log n)에 처리할 수 있어요!
• 최소값, 최대값, 구간 곱 등의 다양한 연산도 효율적으로 수행할 수 있어요.

 

📌 실생활 예시

• 🏦 금융 데이터 분석: 특정 기간 동안 주가의 변동 합을 빠르게 구할 때
• 📊 스포츠 통계: 특정 선수의 경기 점수 합을 효율적으로 계산할 때
• 🏗 도시 교통 모니터링: 특정 구간의 차량 통행량을 빠르게 조회할 때

 

➡ 즉, 세그먼트 트리는 구간 정보를 빠르게 처리하는 데 매우 유용한 자료구조예요!

**세그먼트 트리(Segment Tree)**는 배열의 특정 구간에 대한 쿼리(합, 최소값, 최대값 등)를 빠르게 처리하는 자료구조예요.

 

💡 쉽게 이해하기

• 🏠 건물 층마다 관리 사무실이 있는 아파트를 떠올려 보세요!
  • 각 층(세그먼트)은 여러 세대(배열 요소)를 관리해요.
  • 특정 구간의 정보를 빠르게 찾을 수 있도록 구성돼요.
• 📊 구간 합, 최소값, 최대값을 빠르게 구할 수 있어요.
• ⏳ 시간복잡도는 O(log n)으로 매우 효율적이에요!

 

📌 세그먼트 트리를 활용하면?

1. 배열의 특정 구간 합을 O(log n) 시간 안에 구할 수 있어요.
2. 배열의 특정 원소를 빠르게 수정할 수 있어요.
3. 최소값, 최대값을 구하는 RMQ(Range Minimum Query) 문제를 해결할 수 있어요.

➡ 세그먼트 트리는 구간 쿼리를 최적화하는 중요한 자료구조예요!

---

 

 

🚀 2. 세그먼트 트리의 구조

📌 세그먼트 트리는 기본적으로 이진 트리(Binary Tree) 기반으로 동작해요.

 

💡 트리 구조를 이해하기 쉽게 설명하면?

• 트리의 루트 노드(root node): 전체 배열의 정보를 저장해요.
• 각 내부 노드(internal node): 특정 범위의 값을 저장해요.
• 리프 노드(leaf node): 실제 배열의 개별 원소를 저장해요.

 

📌 배열을 세그먼트 트리로 표현하기 예를 들어, 배열 [1, 3, 5, 7, 9, 11]이 있을 때, 트리는 다음과 같이 구성돼요:

        [전체 합: 36]
       /          \
   [9]            [27]
  /   \         /      \
[4]   [5]   [16]      [11]

• 트리의 루트 노드에는 전체 배열의 합이 저장돼요.
• 왼쪽과 오른쪽으로 쪼개면서 구간 정보를 빠르게 접근할 수 있도록 구성돼요.

 

📌 왜 이렇게 구성할까요?

• 특정 구간의 합을 구할 때 배열을 직접 탐색하는 O(n) 방식 대신, O(log n) 시간에 연산 가능!

➡ 즉, 세그먼트 트리는 데이터를 트리 형태로 저장하여 특정 범위의 정보를 빠르게 조회할 수 있도록 도와주는 자료구조예요!

 

📌 세그먼트 트리는 이진 트리(Binary Tree) 기반으로 동작해요.

• 루트 노드: 전체 배열의 정보를 저장
• 각 자식 노드: 부모 노드의 구간을 절반씩 나누어 저장
• 리프 노드(Leaf Node): 배열의 개별 원소를 저장

 

💡 배열 [1, 3, 5, 7, 9, 11]을 세그먼트 트리로 표현하면?

        [전체 합: 36]
       /          \
   [9]            [27]
  /   \         /      \
[4]   [5]   [16]      [11]

➡ 각 노드는 특정 범위의 합을 저장하고, O(log n) 시간 안에 쿼리를 처리할 수 있어요.

---

 

 

🚀 3. 세그먼트 트리 구현 (구간 합 쿼리)

 

📌 세그먼트 트리의 핵심 연산

1. 트리 생성(Build) - O(n): 처음 한 번만 수행되며, 배열을 트리 형태로 구성해요.
2. 구간 합 계산(Query) - O(log n): 특정 구간의 합을 빠르게 찾을 수 있어요.
3. 값 업데이트(Update) - O(log n): 특정 인덱스의 값을 변경하고, 그에 따라 트리를 갱신해요.

 

💡 비유를 통해 쉽게 이해하기

• 🏠 아파트 관리 시스템에서 특정 동의 전기 사용량을 조회한다고 생각해보세요.
• 세그먼트 트리는 각 동의 사용량 정보를 층별로 나누어 저장하는 구조예요.
• 필요할 때 빠르게 원하는 범위(동 전체, 특정 층 등)의 합을 계산할 수 있어요!

 

📌 구현 코드 예제 (구간 합 쿼리)

 

📌 세그먼트 트리의 핵심 연산

1. 트리 생성 (Build) - O(n)
2. 구간 합 계산 (Query) - O(log n)
3. 값 업데이트 (Update) - O(log n)

 

💡 Python 코드 예제

class SegmentTree:
    """
    세그먼트 트리 클래스
    - 주어진 배열을 기반으로 세그먼트 트리를 구축
    - 특정 범위의 합을 빠르게 계산할 수 있도록 지원
    - 특정 원소 값을 업데이트할 수 있도록 지원
    """
    def __init__(self, arr):
        """
        세그먼트 트리 초기화
        - 배열을 입력받아 트리를 생성
        - 트리 크기는 입력 배열의 4배 크기로 설정
        """
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)  # 4배 크기의 트리 배열 생성
        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, 2 * node + 1, start, mid)
            self.build(arr, 2 * node + 2, mid + 1, end)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def query(self, node, start, end, left, right):
        """
        구간 합을 계산하는 함수
        - 원하는 범위를 입력받아 해당 범위의 값을 반환
        - 범위를 벗어나면 0 반환
        """
        if right < start or end < left:
            return 0  # 범위를 벗어나면 0 반환
        if left <= start and end <= right:
            return self.tree[node]
        mid = (start + end) // 2
        left_sum = self.query(2 * node + 1, start, mid, left, right)
        right_sum = self.query(2 * node + 2, mid + 1, end, left, right)
        return left_sum + right_sum

    def update(self, node, start, end, index, value):
        """
        특정 원소 값을 업데이트하는 함수
        - 새로운 값으로 갱신 후 부모 노드들도 변경된 값을 반영
        """
        if start == end:
            self.tree[node] = value
        else:
            mid = (start + end) // 2
            if start <= index <= mid:
                self.update(2 * node + 1, start, mid, index, value)
            else:
                self.update(2 * node + 2, mid + 1, end, index, value)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

 

💡 사용 예제

arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)
print(st.query(0, 0, len(arr) - 1, 1, 3))  # 출력: 15 (3+5+7)
st.update(0, 0, len(arr) - 1, 1, 10)  # arr[1] 값을 10으로 변경
print(st.query(0, 0, len(arr) - 1, 1, 3))  # 출력: 22 (10+5+7)

➡ 세그먼트 트리를 이용하면 구간 합을 O(log n) 시간 안에 계산할 수 있어요!

---

 

 

🚀 4. 세그먼트 트리의 시간복잡도

 

📌 세그먼트 트리의 연산 속도는?

연산 종류 시간복잡도 설명

트리 생성(Build)	O(n)	배열을 트리로 변환하는 과정
구간 쿼리(Query)	O(log n)	특정 범위의 값을 빠르게 찾을 수 있음
값 업데이트(Update)	O(log n)	특정 원소를 변경할 때 빠르게 반영

 

💡 왜 O(log n)일까요?

• 트리는 이진 구조로 나누어지기 때문에 탐색 깊이가 log n 단계로 줄어들어요.
• 즉, 트리의 높이가 log n이므로, 특정 값에 접근하는 속도가 O(log n)이 돼요.

 

📌 배열을 직접 탐색하는 방식과 비교하면?

• 일반적인 배열 탐색 (O(n)) ❌ → 데이터가 많아지면 매우 비효율적
• 세그먼트 트리 (O(log n)) ✅ → 훨씬 빠르게 원하는 값을 찾을 수 있음

➡ 즉, 세그먼트 트리는 대규모 데이터를 다룰 때 매우 효율적인 자료구조예요!

 

연산 종류 시간복잡도

트리 생성(Build)	O(n)
구간 쿼리(Query)	O(log n)
값 업데이트(Update)	O(log n)

 

📌 왜 O(log n)일까요?

• 트리는 이진 구조로 나누어지기 때문에 탐색 깊이가 log n 단계로 줄어들어요.
• 따라서 배열을 직접 탐색하는 O(n) 방식보다 훨씬 빠릅니다!

➡ 세그먼트 트리는 대규모 데이터를 다룰 때 매우 효율적인 자료구조예요!

---

 

 

✅ 마무리 정리

• 세그먼트 트리는 특정 구간의 합, 최소/최대값을 빠르게 찾을 수 있는 자료구조입니다.
• 배열을 트리 형태로 변환하여, O(log n) 시간 안에 쿼리를 처리할 수 있습니다.
• 구간 쿼리 문제, RMQ(Range Minimum Query) 문제에서 자주 사용됩니다.