세그먼트 트리

세그먼트 트리(Segment Tree)는 구간 합, 최소/최대값 등 특정 범위의 질의를 빠르게 처리할 수 있도록 돕는 자료구조입니다.

 

public class SegmentTree {
    private int[] tree;  // 세그먼트 트리 배열
    private int n;       // 원본 배열 크기

    public SegmentTree(int[] arr) {
        this.n = arr.length;
        // 세그먼트 트리 크기 설정 (4배 크기면 충분)
        tree = new int[4 * n];
        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, 2 * node, start, mid);
            build(arr, 2 * node + 1, mid + 1, end);
            tree[node] = tree[2 * node] + tree[2 * node + 1]; // 합을 저장
        }
    }

    // 특정 구간의 합을 구함
    public int query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    private int query(int node, int start, int end, int l, int r) {
        if (end < l || r < start) { // 범위 밖
            return 0;
        }
        if (l <= start && end <= r) { // 완전히 포함됨
            return tree[node];
        }

        // 일부만 겹침
        int mid = (start + end) / 2;
        int leftSum = query(2 * node, start, mid, l, r);
        int rightSum = query(2 * node + 1, mid + 1, end, l, r);
        return leftSum + rightSum;
    }

    // 특정 인덱스의 값을 변경 (업데이트)
    public void update(int idx, int newValue) {
        update(1, 0, n - 1, idx, newValue);
    }

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

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

        System.out.println(st.query(1, 4)); // [4, 5, 7, 8]의 합 = 24

        st.update(3, 10); // 인덱스 3의 값을 10으로 변경 (7 → 10)

        System.out.println(st.query(1, 4)); // [4, 5, 10, 8]의 합 = 27
    }
}

 

 

 

실제 구현 github :  DataStructure/src/Tree/SegmentTree.java at main · Leekb0804/DataStructure

 

 

 

.