[Week11] Segment Tree

세그먼트 트리란?

세그먼트 트리는 배열과 같이 연속된 구간의 정보를 효율적으로 관리하고 쿼리를 처리하는 데 사용되는 자료구조입니다. 일반적으로 구간 합, 최솟값, 최댓값 등의 쿼리를 빠르게 처리할 수 있습니다.

세그먼트 트리의 특징

1. 구간 쿼리의 빠른 처리: 세그먼트 트리는 구간 쿼리를 O(log N) 시간에 처리할 수 있습니다.
2. 동적 배열 업데이트: 배열의 특정 원소를 업데이트하는 데 O(log N) 시간이 소요됩니다.
3. 메모리 사용: 일반적으로 4N 크기의 메모리를 사용합니다(N은 배열의 크기).

세그먼트 트리의 기본 구조

세그먼트 트리는 트리 구조를 가지며, 각 노드는 특정 구간에 대한 정보를 저장합니다. 루트 노드는 전체 구간을 나타내고, 각 자식 노드는 구간을 절반으로 나눈 서브 구간을 나타냅니다.

세그먼트 트리의 구현

https://velog.io/@jeongbeom4693/Java-세그먼트-트리Segment-Tree

[Java] 세그먼트 트리(Segment Tree)

 

다음은 자바로 세그먼트 트리를 구현한 예제입니다.

1. 세그먼트 트리 초기화

java코드 복사
public class SegmentTree {
    private int[] tree;
    private int n;

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

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

2. 구간 합 쿼리

java코드 복사
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 leftSum = query(2 * node, start, mid, left, right);
    int rightSum = query(2 * node + 1, mid + 1, end, left, right);
    return leftSum + rightSum;
}

3. 업데이트

java코드 복사
public void update(int idx, int value) {
    update(1, 0, n - 1, idx, value);
}

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

사용 예제

java코드 복사
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)); // 3 + 5 + 7 = 15

        // 업데이트
        segmentTree.update(1, 10);
        System.out.println(segmentTree.query(1, 3)); // 10 + 5 + 7 = 22
    }
}

결론

세그먼트 트리는 배열의 구간 합, 최솟값, 최댓값 등의 쿼리를 효율적으로 처리할 수 있는 강력한 자료구조입니다. 자바로 구현한 세그먼트 트리는 위와 같은 기본 구조와 메서드를 통해 쉽게 사용할 수 있습니다. 취업을 위한 코딩 테스트에서 세그먼트 트리를 활용하면 높은 효율성을 요구하는 문제를 효과적으로 해결할 수 있을 것입니다.