Segment Tree <세그먼트 트리>

세그먼트트리

class SegmentTree {
    long tree[]; // 세그먼트 트리 배열
    int treeSize; // 트리의 크기

    // 세그먼트 트리 생성자
    public SegmentTree(int arrSize) {
        // 배열 크기에 맞게 트리의 높이 계산
        int h = (int) Math.ceil(Math.log(arrSize) / Math.log(2));
        // 트리의 크기 계산
        this.treeSize = (int) Math.pow(2, h + 1);
        // 트리 배열 생성
        this.tree = new long[treeSize];
    }

    // 세그먼트 트리 초기화 메서드
    public long init(long[] arr, int node, int start, int end) {
        // 시작과 끝이 같으면 leaf 노드이므로 해당 값으로 초기화
        if (start == end) {
            return tree[node] = arr[start];
        }
        // leaf 노드가 아니면, 자식 노드의 합을 저장
        return tree[node] = init(arr, node * 2, start, (start + end) / 2)
                + init(arr, node * 2 + 1, (start + end) / 2 + 1, end);
    }

    // 세그먼트 트리 값 갱신 메서드
    public void update(int node, int start, int end, int idx, long diff) {
        if (idx < start || end < idx) return;
        // 차이를 현재 노드에 반영
        tree[node] += diff;
        // leaf 노드가 아니면 자식 노드도 갱신
        if (start != end) {
            update(node * 2, start, (start + end) / 2, idx, diff);
            update(node * 2 + 1, (start + end) / 2 + 1, end, idx, diff);
        }
    }

    // 세그먼트 트리 구간 합 계산 메서드
    public long sum(int node, int start, int end, int left, int right) {
        // 범위가 벗어나면 0 반환
        if (left > end || right < start) return 0;
        // 범위가 완전히 포함되면 해당 노드 값 반환
        if (left <= start && end <= right) return tree[node];
        // 그 외의 경우 좌/우측으로 분할하여 계산
        return sum(node * 2, start, (start + end) / 2, left, right)
                + sum(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
    }
}


//====================================================================================

// 같은코드 압축된 코드

class SegmentTree {
    long tree[];
    int treeSize;

    public SegmentTree(int arrSize) {
        int h = (int) Math.ceil(Math.log(arrSize) / Math.log(2));
        treeSize = (int) Math.pow(2, h + 1);
        tree = new long[treeSize];
    }

    public long init(long[] arr, int node, int start, int end) {
        return start == end ? tree[node] = arr[start] : (tree[node] = init(arr, node * 2, start, (start + end) / 2) + init(arr, node * 2 + 1, (start + end) / 2 + 1, end));
    }

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

    public long sum(int node, int start, int end, int left, int right) {
        if (left > end || right < start) return 0;
        return (left <= start && end <= right) ? tree[node] : (sum(node * 2, start, (start + end) / 2, left, right) + sum(node * 2 + 1, (start + end) / 2 + 1, end, left, right));
    }
}

 

세그먼트 트리는 배열 또는 리스트와 같은 데이터 구조를 사용하여 구간에 대한 질의를 효율적으로 처리하는 자료구조입니다. 이를 통해 주어진 구간에 대한 최솟값, 최댓값 또는 합 등을 빠르게 계산할 수 있습니다. 보통 이진 트리의 형태를 가지며, 재귀적으로 구간을 분할하여 각 구간의 값을 저장하고 관리합니다.

 

logN 의시간이 걸리며 수정이되면 수정이 전체 트리에 반영된다.

 

변경에도 M번 변경시 M(logN) 의 시간이 걸린다.