🔥 알고리즘 끝판왕, 세그먼트 트리로 구간 문제 완벽 정복하기! 💪

세그먼트 트리(Segment Tree) 🌳

세그먼트 트리(Segment Tree)는 주로 구간 쿼리(range query)와 구간 업데이트(range update)를 효율적으로 처리하는 자료 구조입니다. 세그먼트 트리는 이진 트리 구조를 가지며, 각 노드는 특정 구간의 값을 저장해 구간합, 최솟값, 최댓값 등을 빠르게 계산할 수 있어요. ⚡

---

세그먼트 트리의 구성 🏗️

세그먼트 트리는 배열의 값을 트리 형태로 표현한 자료 구조로, 각 노드는 배열의 부분 구간을 나타냅니다.

• 리프 노드 🍃: 배열의 각 원소가 리프 노드에 저장됩니다.
• 내부 노드 🌿: 내부 노드는 자신이 나타내는 구간의 값을 저장합니다. 예를 들어, 구간 합 세그먼트 트리에서는 해당 구간의 합을 저장해요.

---

세그먼트 트리의 특징 🧐

1. 트리의 높이 ⬆️: 세그먼트 트리는 이진 트리이므로 높이는 배열의 크기 (n)에 대해 (log n)에 비례합니다.
2. 공간 복잡도 💾: 배열 크기가 (n)일 때, 세그먼트 트리는 약 (4n)개의 노드를 사용합니다.
3. 시간 복잡도 ⏱️:
   • 구간 합 또는 구간 최소/최대 등의 쿼리를 수행하는 데 (O(log n)) 시간이 소요됩니다.
   • 업데이트 작업도 (O(log n)) 시간이 걸립니다.

---

세그먼트 트리의 사용 방법 🛠️

1. 세그먼트 트리 생성 🌱

세그먼트 트리는 배열을 기반으로 생성되며, 트리로 변환하는 데 (O(n)) 시간이 소요됩니다.

def build_segment_tree(arr, tree, node, start, end):
    if start == end:
        # 리프 노드에 배열의 값을 저장
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        # 왼쪽 자식 노드
        build_segment_tree(arr, tree, 2 * node, start, mid)
        # 오른쪽 자식 노드
        build_segment_tree(arr, tree, 2 * node + 1, mid + 1, end)
        # 부모 노드는 자식 노드들의 값을 합침
        tree[node] = tree[2 * node] + tree[2 * node + 1]

2. 구간 쿼리 🔍

원하는 구간 [L, R]의 값을 찾기 위해 트리에서 구간 쿼리를 수행합니다.

def range_query(tree, node, start, end, L, R):
    if R < start or end < L:
        # 구간이 완전히 겹치지 않으면 무시
        return 0
    if L <= start and end <= R:
        # 구간이 완전히 포함되면 현재 노드 값을 반환
        return tree[node]
    
    # 부분적으로 겹치는 경우 자식 노드로 쿼리 분할
    mid = (start + end) // 2
    left_sum = range_query(tree, 2 * node, start, mid, L, R)
    right_sum = range_query(tree, 2 * node + 1, mid + 1, end, L, R)
    
    return left_sum + right_sum

3. 값 업데이트 📊

배열의 특정 값을 변경할 때, 해당 값이 포함된 구간의 노드들도 업데이트합니다.

def update(tree, node, start, end, idx, val):
    if start == end:
        # 리프 노드 업데이트
        tree[node] = val
    else:
        mid = (start + end) // 2
        if start <= idx <= mid:
            # 왼쪽 자식 노드 업데이트
            update(tree, 2 * node, start, mid, idx, val)
        else:
            # 오른쪽 자식 노드 업데이트
            update(tree, 2 * node + 1, mid + 1, end, idx, val)
    
        # 부모 노드는 자식 노드들의 값으로 다시 계산
        tree[node] = tree[2 * node] + tree[2 * node + 1]

---

세그먼트 트리의 응용 🎯

세그먼트 트리는 다양한 문제에 활용될 수 있습니다. 예를 들어:

• 구간 합 문제 ➕: 배열의 특정 구간의 합을 빠르게 구할 수 있습니다.
• 구간 최소/최대 문제 🔽🔼: 배열의 특정 구간에서 최소값 또는 최대값을 빠르게 찾을 수 있어요.
• 구간 업데이트 문제 🛠️: 배열의 특정 구간의 값을 일괄적으로 변경하는 문제에도 응용할 수 있습니다.

세그먼트 트리는 이렇게 시간 복잡도 (O(log n))로 효율적으로 동작해, 큰 데이터셋에서도 성능을 보장할 수 있습니다. 💡