[Algorithm Tech] Segment Tree(세그먼트 트리)

* 세그먼트 트리

배열이 주어졌을 때 해당 배열을 완전 이진 트리 Leaf Node에 넣고 Leaf Node의 부모 노드에 합/곱/Max/Min을 올려가는 방식이다.

A 배열의 부분 합을 구할때 배열의 값이 변하거나 테스트 케이스가 많을 경우(쿼리가 많을 경우) 시간 복잡도가 한 쿼리당 O(logN)으로 계산할 수 있다.

* 세그먼트 트리에서 값을 저장하는 방식

부모 노드가 n 번째 노드라면 n*2, n*2+1 번째 노드를 자식노드로 가진다는 특성을 이용하여 1차원 배열에 저장한다.

처음 입력받는 값들은 Leaf Node이기 때문에 뒤쪽 배열에 값을 저장하고,

자식노드가 n 번째 노드라면 n/2 번째 부모 노드에 트리방식에 따라 합/곱/Max/Min을 저장한다. 이 때의 시간복잡도는 O(logN)이다.

Leaf Node의 값을 변경하게 된다면 트리방식에 따라 부모 노드들을 수정하면 된다. 이때 시간 복잡도는 O(logN)이 된다.

* 소스 코드

class SegmentTree {
    long[] tree;
    int s;
 
    public SegmentTree(int n) {
        for (s = 1; s < n; s *= 2) ;
        tree = new long[s * 2];
        for (int i = 1; i < s + s; i++)
            tree[i] = 0l;
    }
 
    void update(int x, long v) {
        int l = x + s - 1;
        tree[l] = v;
        l /= 2;
        while (l >= 1) {
            tree[l] = tree[l * 2] + tree[l * 2 + 1];
            l /= 2;
        }
    }
 
    long getMin(int Left, int Right) {
        int l = Left + s - 1, r = Right + s - 1;
        long rval = Long.MAX_VALUE;
        while (l <= r) {
            if (l % 2 == 0) l /= 2;
            else {
                rval = Math.min(rval, tree[l]);
                l = (l / 2) + 1;
            }
            if (r % 2 == 1) r /= 2;
            else {
                rval = Math.min(rval, tree[r]);
                r = (r / 2) - 1;
            }
        }
        return rval;
    }
 
    long getSum(int Left, int Right) {
        int l = Left + s - 1, r = Right + s - 1;
        long rval = 0;
        while (l <= r) {
            if (l % 2 == 0) l /= 2;
            else {
                rval += tree[l];
                l = (l / 2) + 1;
            }
            if (r % 2 == 1) r /= 2;
            else {
                rval += tree[r];
                r = (r / 2) - 1;
            }
        }
        return rval;
    }
}

출처 : https://www.codeground.org/

* 참고 문제

백준/2042 :: 구간 합 구하기

백준/1275 :: 커피숍2