세그먼트 트리 (Segment Tree)의 개념 및 구현

세그먼트 트리 (Segment Tree)의 개념 및 구현

세그먼트 트리(Segment Tree)는 배열과 같은 데이터 구조에서 특정 구간의 데이터를 효율적으로 질의(Query)하고 업데이트(Update)할 수 있도록 설계된 트리 기반의 자료 구조입니다. 주로 구간 합(Sum), 구간 최소값(Minimum), 구간 최대값(Maximum) 등과 같은 질의를 빠르게 처리하는 데 사용됩니다.

---

1. 세그먼트 트리의 개념

1.1 세그먼트 트리란?

• 세그먼트 트리는 주어진 배열을 기반으로, 배열의 구간별 정보를 저장하는 완전 이진 트리입니다.
• 각 노드는 특정 범위에 대한 값을 나타내며, 이를 통해 구간 질의와 업데이트를 O(log N) 시간 복잡도로 수행할 수 있습니다.
• 일반적으로 세그먼트 트리는 정적 배열에 대해 사용됩니다.

---

1.2 세그먼트 트리의 구조

1. 리프 노드(Leaf Node): 입력 배열의 원소를 나타냅니다.
2. 내부 노드(Internal Node): 자식 노드의 값을 기반으로 계산된 구간 정보를 저장합니다.
   • 예: 구간 합 트리에서는 내부 노드가 자식 노드의 합을 저장합니다.

1.3 주요 기능

1. 구간 질의(Query):
   • 배열의 특정 구간 [L, R]의 값을 빠르게 구합니다.
2. 점 업데이트(Update):
   • 배열의 특정 인덱스 값을 변경하고, 트리를 갱신합니다.

---

2. 세그먼트 트리의 구현

2.1 세그먼트 트리의 생성

• 트리 크기: 입력 배열 크기를 N이라 할 때, 세그먼트 트리의 최대 크기는 4 * N입니다.
• 트리의 루트 노드(인덱스 1)는 전체 배열의 구간을 나타냅니다.

---

2.2 세그먼트 트리 구현 (C#)

using System;

public class SegmentTree
{
    private int[] tree;  // 세그먼트 트리를 저장할 배열
    private int n;       // 입력 배열 크기

    public SegmentTree(int[] input)
    {
        n = input.Length;
        tree = new int[4 * n];
        BuildTree(input, 0, n - 1, 1); // 트리 생성
    }

    // 세그먼트 트리 생성
    private void BuildTree(int[] input, int start, int end, int node)
    {
        if (start == end)
        {
            tree[node] = input[start]; // 리프 노드
        }
        else
        {
            int mid = (start + end) / 2;
            BuildTree(input, start, mid, 2 * node);       // 왼쪽 자식
            BuildTree(input, mid + 1, end, 2 * node + 1); // 오른쪽 자식
            tree[node] = tree[2 * node] + tree[2 * node + 1]; // 부모 노드에 값 저장
        }
    }

    // 구간 합 질의 [L, R]
    public int Query(int l, int r)
    {
        return Query(0, n - 1, 1, l, r);
    }

    private int Query(int start, int end, int node, int l, int r)
    {
        if (r < start || end < l) // 범위 밖
            return 0;
        if (l <= start && end <= r) // 범위 안
            return tree[node];

        int mid = (start + end) / 2;
        int leftSum = Query(start, mid, 2 * node, l, r);
        int rightSum = Query(mid + 1, end, 2 * node + 1, l, r);
        return leftSum + rightSum; // 구간 합 반환
    }

    // 배열의 특정 인덱스 업데이트
    public void Update(int index, int value)
    {
        Update(0, n - 1, 1, index, value);
    }

    private void Update(int start, int end, int node, int index, int value)
    {
        if (start == end)
        {
            tree[node] = value; // 리프 노드 값 변경
        }
        else
        {
            int mid = (start + end) / 2;
            if (index <= mid)
                Update(start, mid, 2 * node, index, value);
            else
                Update(mid + 1, end, 2 * node + 1, index, value);

            tree[node] = tree[2 * node] + tree[2 * node + 1]; // 부모 노드 갱신
        }
    }
}

// 사용 예제
public class Program
{
    public static void Main()
    {
        int[] array = { 1, 3, 5, 7, 9, 11 };
        SegmentTree segTree = new SegmentTree(array);

        Console.WriteLine("구간 합 (1~3): " + segTree.Query(1, 3)); // 결과: 15
        segTree.Update(1, 10); // 배열[1] = 10
        Console.WriteLine("구간 합 (1~3): " + segTree.Query(1, 3)); // 결과: 22
    }
}

 

---

3. 시간 복잡도

1. 구간 질의(Query): O(log N)
   • 트리의 높이만큼 탐색.
2. 업데이트(Update): O(log N)
   • 수정된 값이 포함된 구간을 재계산.
3. 트리 생성(Build): O(N log N)

---

4. 세그먼트 트리의 활용

• 구간 합(Sum): 특정 구간의 합 계산.
• 구간 최소값/최대값(Min/Max): 특정 구간의 최솟값 또는 최댓값 찾기.
• 구간 곱(Product): 특정 구간의 곱 계산.
• 2D 구간 질의: 2차원 배열에 대한 구간 질의와 업데이트.

---

5. 세그먼트 트리의 한계

1. 동적 크기 조정이 어렵습니다. 크기를 변경하려면 새로 트리를 생성해야 합니다.
2. 구현이 복잡해지는 경향이 있습니다.
3. 일반적으로 펜윅 트리(Fenwick Tree)보다 메모리 사용량이 큽니다.

---

세그먼트 트리는 다양한 문제에서 강력한 도구로 사용됩니다.
특히, 대규모 배열 데이터에 대해 빠른 구간 연산이 필요한 경우 효율적인 해결책을 제공합니다.