[Python] 세그먼트 트리 segment tree

[세그먼트 트리] 세그먼트 트리 알고리즘 정리

📌 세그먼트 트리란?

세그먼트 트리는 배열의 구간 정보를 저장하여 구간 쿼리와 업데이트를 효율적으로 처리하는 자료구조입니다. 주로 구간 합, 최소값, 최대값 등을 O(log n) 시간 안에 계산할 수 있도록 도와줍니다.

🚨 세그먼트 트리의 구조

• 완전 이진 트리: 배열을 기반으로 한 완전 이진 트리 구조로 구현됩니다.
• 노드 역할:
  • 리프 노드: 배열의 개별 원소를 저장합니다.
  • 내부 노드: 자식 노드의 값을 이용해 해당 구간의 정보를(예, 최소값 또는 합) 계산해 저장합니다.

💡 주요 연산

1. 구간 쿼리: 특정 구간(예, [L, R])의 합 또는 최소/최대값을 O(log n) 시간 내에 계산할 수 있습니다.
2. 업데이트: 배열의 한 원소가 변경되었을 때, O(log n) 시간 안에 트리 전체에 반영할 수 있습니다.

Tip:
리프 노드의 개수를 “N 이상의 최소 2의 거듭제곱”으로 맞추면, 트리의 높이가 일정해지고 인덱스 계산이 단순해집니다.
(예: leaf_start = 2**math.ceil(math.log2(N)))

📚 예제 코드 (구간 최소값)

아래 코드는 구간 최소값을 구하는 세그먼트 트리의 구현 예제입니다. (구간 합 쿼리 및 업데이트 구현도 유사한 방식으로 작성할 수 있습니다.)

 

import math

def build_min_tree(arr):
    n = len(arr)
    # 리프 노드 시작 인덱스: n 이상의 최소 2의 거듭제곱
    leaf_start = 2 ** math.ceil(math.log2(n))
    tree_size = 2 * leaf_start
    # 구간 최소값을 위한 초기값은 무한대로 설정
    tree = [float('inf')] * tree_size

    # 리프 노드에 배열 값 채워넣기
    tree[leaf_start:leaf_start + n] = arr[:]

    # 내부 노드 채우기: 자식 노드의 최소값으로 부모 노드 결정
    for i in range(leaf_start - 1, 0, -1):
        tree[i] = min(tree[2 * i], tree[2 * i + 1])

    return tree, leaf_start

def update_min_tree(tree, leaf_start, index, value):
    # index: 원본 배열의 0-based 인덱스
    pos = leaf_start + index
    tree[pos] = value
    pos //= 2
    while pos >= 1:
        tree[pos] = min(tree[2 * pos], tree[2 * pos + 1])
        pos //= 2

def query_min_tree(tree, leaf_start, query_left, query_right):
    # query_left, query_right: 0-based 인덱스로 구간 지정
    left = leaf_start + query_left
    right = leaf_start + query_right
    result = float('inf')
    while left <= right:
        if left % 2 == 1:
            result = min(result, tree[left])
            left += 1
        if right % 2 == 0:
            result = min(result, tree[right])
            right -= 1
        left //= 2
        right //= 2
    return result

 

예제 실행

 

if name == 'main':
arr = [5, 3, 8, 6, 2, 7, 4]
tree, leaf_start = build_min_tree(arr)

# 인덱스 1~5 구간의 최소값 조회 (0-based 인덱스)
print("초기 구간 최소값 (인덱스 1~5):", query_min_tree(tree, leaf_start, 1, 5))

# 인덱스 3의 값을 1로 업데이트
update_min_tree(tree, leaf_start, 3, 1)
print("업데이트 후 구간 최소값 (인덱스 1~5):", query_min_tree(tree, leaf_start, 1, 5))

---

🎯 세그먼트 트리의 핵심 포인트

1. 효율적인 구간 쿼리: O(log n) 시간 내에 구간 정보를 조회할 수 있습니다.
2. 빠른 업데이트: 특정 원소의 변경 사항이 O(log n) 시간 내에 트리에 반영됩니다.
3. 메모리 사용: 트리 전체는 일반적으로 O(n) 공간을 사용합니다.

---

✨ 스터디를 통해 얻은 인사이트

1. 구조와 동작 원리: 리프 노드부터 시작해 내부 노드를 채워 나가는 방식과 인덱스 계산 방식을 이해했습니다.
2. 실제 문제 적용: 세그먼트 트리를 활용하여 구간 쿼리 문제를 효율적으로 해결할 수 있는 가능성을 확인했습니다.
3. 코드 최적화: 메모리 관리 및 연산 효율성을 고려한 구현 방법에 대해 배웠습니다.

---

🔍 코드 설명

• build_min_tree
  입력 배열을 기반으로 세그먼트 트리를 구성합니다.
  • 리프 노드를 “n 이상의 최소 2의 거듭제곱” 크기로 할당하여, 인덱스 계산을 단순화합니다.
  • 내부 노드는 자식 노드의 최소값으로 채워집니다.
• update_min_tree
  배열의 특정 인덱스 값을 업데이트한 후, 부모 노드들에 변경 사항을 전파합니다.
• query_min_tree
  주어진 구간 내의 최소값을 효율적으로 계산합니다.

---

이 글이 세그먼트 트리의 원리와 구현 방법을 이해하는 데 도움이 되길 바랍니다.
세그먼트 트리는 다양한 문제 상황에서 강력한 도구가 될 수 있으니, 여러 문제에 직접 적용해 보며 익혀보세요!