세그먼트 트리(Segment Tree)

세그먼트 트리를 적용할 수 있는 문제는 크게 다음과 같다

• 구간 합 구하기 (Range Sum Query)
• 구간 최소값/최대값 구하기 (Range Min/Max Query)
• 특정 원소 업데이트 후 구간 쿼리 (Point update + range query)
• 커다란 배열에서 반복적으로 합/최소/최대 등을 구하는 문제

---

전체코드

public class SegmentTree {
    int[] tree;
    int n;

    // 구간 합
    public SegmentTree(int[] arr) {
        this.n = arr.length;
        int height = (int)Math.ceil(Math.log(n) / Math.log(2));
        int size = 1 << (height + 1);
        tree = new int[size];
        build(arr, 1, 0, n - 1);
    }

    private void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, node * 2, start, mid);
            build(arr, node * 2 + 1, mid + 1, end);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }

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

    private int query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) {
            return 0; // 합에서 영향 없음
        }

        if (left <= start && end <= right) {
            return tree[node]; // 현재 노드 값 그대로 리턴
        }

        int mid = (start + end) / 2;
        int l = query(node * 2, start, mid, left, right);
        int r = query(node * 2 + 1, mid + 1, end, left, right);
        return l + r;
    }

    public void update(int idx, int newValue) {
        update(1, 0, n - 1, idx, newValue);
    }

    public void update(int node, int start, int end, int idx, int val) {
        if (idx < start || end < idx) {
            return;
        }
        if (start == end) {
            tree[node] = val;
            return;
        }

        int mid = (start + end) / 2;
        update(node * 2, start, mid, idx, val);
        update(node * 2 + 1, mid + 1, end, idx, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

---

public SegmentTree(int[] arr)

public SegmentTree(int[] arr) {
        this.n = arr.length;
        int height = (int)Math.ceil(Math.log(n) / Meth.log(2));
        int size = 1 << (height + 1);
        tree = new int[size];
        build(arr, 1, 0, n - 1);
    }

세그먼트 트리는 완전 이진트리로 높이가 log₂(n) 형태로 되어야한다.
size를 계산할 때 2^x을 의미하는 비트 시프트 연산을 사용하여 노드의 시작을 1로 하기 때문에 +1을 한다.

build는 세그먼트 트리를 재귀적으로 생성하는 함수로 node = 1부터 시작해서, arr[0] ~ arr[n - 1] 범위를 다루는 세그먼트 트리를 구성한다.

---

private void build(int[] arr, int node, int start, int end)

private void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, node * 2, start, mid);
            build(arr, node * 2 + 1, mid + 1, end);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }

arr: 입력 배열 (리프 노드에 들어갈 원래 값들)
node: 세그먼트 트리의 현재 노드 번호 (루트 1번)
start, end: 현재 노드가 담당하는 구간 (arr[start] ~ arr[end])

기저사례는 리프 노드에 도달한 경우 (하나의 원소만 포함하는 구간)

mid: 현재 구간을 왼쪽, 오른쪽으로 나뉙 위해 가운데 인덱스를 구함

왼쪽 자식: node 2, 범위: [start ~ mid]
오른쪽 자식: node 2 + 1, 범위: [mid + 1 ~ end]

tree[node]: 자식 노드들이 리턴되고, 현재 노드의 값은 두 자식의 값을 더해서 저장한다.

다음과 같은 구간 합 예시가 있다.

         [1] → arr[0~3]
        /    \
     [2]      [3]
   /   \     /   \
[4]  [5]  [6]   [7]
(2)  (4)  (5)   (7)

1. tree[2] = 2 + 4 = 6
2. tree[3] = 5 + 7 = 12
3. tree[1] = 6 + 12 = 18

---

public int query(int left, int right)

특정 구간 합을 구하는 메서드

left, right: 구간 쿼리 범위 (arr[left] ~ arr[right] 구간의 합)

private int query(int node, int start, int end, int left, int right) {
    // 1. [start~end]와 [left~right]가 전혀 겹치지 않음 (무관한 구간)
    if (right < start || end < left) {
        return 0; // 합에서 영향 없음
    }

    // 2. [start~end]가 [left~right]에 완전히 포함됨
    if (left <= start && end <= right) {
        return tree[node]; // 현재 노드 값 그대로 리턴
    }

    // 3. 일부만 겹칠 경우 → 자식 노드 쿼리로 나눠서 내려감
    int mid = (start + end) / 2;
    int l = query(node * 2, start, mid, left, right);
    int r = query(node * 2 + 1, mid + 1, end, left, right);
    return l + r;
}

node: 현재 세그먼트 트리 노드 번호 (루트 1)
start, end: 이 노드가 담당하는 배열 범위
left, right: 사용자가 요청한 구간

---

public void update(int idx, int newValue)

세그먼트 트리에서 특정 인덱스의 값을 변경하고, 트리의 값을 아래에서 위로 갱신하는 메서드

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

node: 현재 세그먼트 트리 노드 번호
start ~ end: 현재 노드가 담당하는 배열 범위
idx: 업데이트할 배열 인덱스
value: 새로 바꿀 값

1. 현재 노드 범위에 idx가 포함되지 않으면 무시

2. 리프 노드에 도달한 경우, 실제 값을

3. 자식 노드로 내려가서 재귀적으로 처리 후, 현재 노드 값을 갱신

---

예제

public static void main(String[] args) {
        int[] arr = {2, 4, 5, 7, 8, 9};
        SegmentTree segTree = new SegmentTree(arr);

        System.out.println("=== 세그먼트 트리 구조 ===");
        segTree.printTree();

        System.out.println("\n=== 구간합 쿼리: [1~3] ===");
        System.out.println("합 = " + segTree.query(1, 3)); // 4+5+7 = 16

        System.out.println("\n=== 인덱스 2 값을 10으로 변경 ===");
        segTree.update(2, 10); // arr[2] = 10

        System.out.println("\n=== 수정 후 세그먼트 트리 구조 ===");
        segTree.printTree();

        System.out.println("\n=== 구간합 쿼리: [1~3] ===");
        System.out.println("합 = " + segTree.query(1, 3)); // 4+10+7 = 21
    }

1. 구간합을 계산 (1~3 까지 범위에서)4
   

2. 인덱스 2 값을 10으로 변경
   

수정 과정에서는 루트 노드에서 부터 리프 노드로 내려간 후 리프 노드 값을 갱신하고 차례대로 리프노드의 부모 노드를 갱신하는 방향으로 값 수정이 이루어진다.

---

브루트포스와 성능 비교

구간 합 구하기 2042번
https://www.acmicpc.net/problem/2042

이 문제를 브루트포스와 세그먼트트리를 사용한 방법의 성능을 비교한다.

브루트 포스의 경우 O(Q × N) 으로 쿼리 20,000 * 1,000,000 = 20,000,000,000회의 연산이 들어간다. 1억에 1초로 잡았을 때 200초가 걸린다.

세그먼트 트리의 경우 O(N + Q × log N) 으로 1,000,000+20,000×log 1,000,000 약 400만 회의 연산이 걸린다. 이 경우에는 0.4초로 2초 안에 안전하게 들어온다!