세그먼트 트리(Segment Tree, 구간 트리)

세그먼트 트리(Segment Tree, 구간 트리)

■ 구간에 대한 질문에 효율적으로 대답하는 것

■ Segment Tree는 저장된 자료들을 적절히 전처리하여 그들에 대한 질의에 빠르게 대답할 수 있도록 한다.

■ 구간 트리의 핵심 아이디어는 주어진 배열의 구간들을 표현하는 이진트리를 만드는 것

전처리하는게 핵심인 것 같습니다.

만약 구간의 최소값을 여러번 구하는 것이 목적이라면, 그 목적에 맞게 전처리하여 구간 트리를 구현하는 것입니다.

그리고 그 구간 트리는 해당 구간의 최소치를 각 노드에 저장할 것입니다.

예) 길이 5인 배열을 표현하는 구간 트리가 저장하는 구간들

[0, 4]

[0, 2]    [3, 4]

   [0, 1][2]    [3][4]

   [0][1]

■ Heap 자료구조와 마찬가지로 일차원 배열로 표현하는 것이 간단

(루트 노드는 1번, 노드 i의 왼쪽 자식은 2i, 오른쪽 자식은 2i + 1)

■ 배열의 길이 : n이상의 2의 거듭제곱 * 2

(n=6인경우 13이 필요함, 8 * 2 = 16)

2^x > N

x > log_2_N

x > logN / log2

x = ceil(logN / log2)

■ 시간 복잡도 O(logN)

---

구간의 합을 구하는 Segment Tree 예제를 한번 구현해봤습니다.

Segment Tree를 의미하는 1차원 배열의 각 값은 해당 구간의 합이 될 것입니다.

int[] arr = {5, 3, 7, 9, 6, 4, 1, 2, 1}일 때

결과값

[0, 38, 30, 8, 15, 15, 5, 3, 8, 7, 9, 6, 4, 1, 2, 1, 5, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

그림으로 나타내보면

import java.io.IOException;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {

        int[] arr = {5, 3, 7, 9, 6, 4, 1, 2, 1};

        SegmentTree segmentTree = new SegmentTree(arr, 9);

        System.out.println(Arrays.toString(segmentTree.segmentArr));
    }
}

class SegmentTree {

    int[] segmentArr; // The array that stores segment tree nodes

    SegmentTree(int[] arr, int n) {

        //int x = (int) Math.ceil(Math.log(n) / Math.log(2));

        //int segmentSize = (int) Math.pow(2, x) * 2 - 1;

        //segmentArr = new int[segmentSize];
        segmentArr = new int[n * 4];

        init(arr, 0, n - 1, 1);
    }

    // node를 root로 하는 서브트리를 초기화하고, 이 구간의 최소치를 반환한다
    int init(int[] arr, int left, int right, int node) {

        if (left == right) {

            return segmentArr[node] = arr[left];
        }

        int mid = (left + right) / 2;

        segmentArr[node] += init(arr, left, mid, node * 2);
        segmentArr[node] += init(arr, mid + 1, right, node * 2 + 1);

        return segmentArr[node];
    }
}