세그먼트 트리에 관하여

세그먼트 트리는 구간 쿼리를 효율적으로 처리하기 위한 트리 형태의 자료구조로, 배열 내 특정 범위의 합, 최소값, 최대값 등의 연산을 빠르게 수행할 수 있습니다.

---

 

1. 세그먼트 트리의 구조

세그먼트 트리는 배열을 구간 단위로 나누어 트리 형태로 표현합니다. 트리의 각 노드는 배열의 특정 구간을 나타내며, 노드의 값은 해당 구간의 연산(합, 최소값 등) 결과를 저장합니다.

• 장점: 구간 연산을 효율적으로 수행 가능
• 단점: 메모리 사용량이 높음

---

2. 세그먼트 트리의 동작 원리

세그먼트 트리는 크게 다음 두 가지 연산을 지원합니다.

구간 질의(Query)

• 특정 구간에 대한 합, 최소값, 최대값 등의 값을 빠르게 얻을 수 있습니다.

값 갱신(Update)

• 특정 위치의 값을 변경하면 연관된 모든 노드의 값을 갱신합니다.

---

3. 시간 복잡도

• 구간 질의(Query): O(logN)
• 값 갱신(Update): O(logN)

---

4. 세그먼트 트리 구현 (Java)

public class SegmentTree {
    private int[] tree;
    private int size;

    public SegmentTree(int[] arr) {
        size = arr.length;
        tree = new int[size * 4];
        buildTree(arr, 0, size - 1, 1);
    }

    private void buildTree(int[] arr, int left, int right, int node) {
        if (left == right) {
            tree[node] = arr[left];
            return;
        }
        int mid = (left + right) / 2;
        buildTree(arr, left, mid, node * 2);
        buildTree(arr, mid + 1, right, node * 2 + 1);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    public int query(int left, int right) {
        return query(0, size - 1, 1, left, right);
    }

    private int query(int start, int end, int node, int left, int right) {
        if (left > end || right < start) return 0;
        if (left <= start && end <= right) return tree[node];
        int mid = (start + end) / 2;
        return query(start, mid, node * 2, left, right)
                + query(mid + 1, end, node * 2 + 1, left, right);
    }

    public void update(int index, int value) {
        update(0, size - 1, 1, index, value);
    }

    private void update(int start, int end, int node, int index, int value) {
        if (index < start || index > end) return;
        if (start == end) {
            tree[node] = value;
            return;
        }
        int mid = (start + end) / 2;
        update(start, mid, node * 2, index, value);
        update(mid + 1, end, node * 2 + 1, index, value);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree segmentTree = new SegmentTree(arr);

        System.out.println(segmentTree.query(1, 3)); // 15

        segmentTree.update(1, 10);

        System.out.println(segmentTree.query(1, 3)); // 22
    }
}

---

5. 마무리

세그먼트 트리는 효율적인 구간 연산을 제공하며 다양한 알고리즘 문제 해결과 시스템 최적화에 널리 사용됩니다.

• 범위 합, 최소값, 최대값 쿼리
• 데이터의 잦은 업데이트 및 질의가 필요한 시스템
• 경쟁 프로그래밍에서의 효율적인 데이터 처리