[트리] Tree 6: Segment Tree구간 트리 , RMQ, 펜윅 트리(이진 인덱스 트리)

(일반적인 구간트리와는 다른 자료구조, 책에서는 알고리즘 문제를 풀기위한 자료구조를 설명한다.) 

(일반적인 구간트리는 1차원 좌표상의 구간들을 지정하고 특정 위치를 포함하는 구간들을 찾는 자료구조임.)

 

1. 구간 트리(segment Tree)

 

 

구간 트리는 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록한다.

(일차원 배열의 특정 구간)

 

ex) 구간의 최소치를 여러번 구하는 문제.

            어떤 배열 A의 부분 구간의 최소치를 찾는데 보통 부분 구간을 순회하며 최소치를 찾는다, 이것은 O(N)의 시간이 걸린다.

            반면 한번의 전처리를 통해 구간트리를 생성하면, 연산을 더 빠르게 할 수 있다.

 

구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다.

 

구간 트리의 루트는 항상 배열의 전체 구간 [0, n -1]을 표현하며,

한 트리의 왼쪽 자식과 오른쪽 자식은 각각 해당 구간의 왼쪽 반과 오른쪽 반을 표현한다.

길이가 1 인 구간을 표현하는 노드들인 리프가 된다.

 

(0, 7)
(0,3)					(4, 7)
(0,1)			(2,3)		(4,5)			(6,7)
0	1		2	3	4	5		6	7

 

구간 트리는 노드마다 해당 구간에 대한 계산 결과를 미리 저장해 둔다.

(최소치 문제에서는 최소치를 저장)

 

트리를 만들고 나면 어떤 구간[i, j]이 주어지더라도, 이 구간을 구간 트리의 노드에 포함된 구간들의

합집합으로 표현할 수 있다.

 

[2, 7]의 구간이 주어지면 [2,3] , [4, 7] 구간으로 표현할 수 있는 것이다.

 

 

 

2. 구간 최소 쿼리 (Range minimum query, RMQ)

 

특정 구간의 최소치를 찾는 문제 

 

구간트리는 위의 표와 같이 힙과같이 거의 균형잡힌 모양이다. (절반씩 구간을 나누기 때문)

 

이러한 성질 덕분에 일차원 배열로 표현하는데 어려움이 없다.

 

루트     = 1

노드     = i

왼쪽     = 2*i

오른쪽  = 2*i + 1

 

배열의 길이: n을 가장가까운 2의 거듭제곱으로 올림한 뒤 2를 곱한다. (6 -> 8 -> 16) or 4n

 

구간 트리의 초기화

 

각 노드마다 해당 구간의 최소치를 계산하는 함수 init()를 구현한다.

 

이 함수는 현재 구간을 두 개로 나눠 재귀호출한 뒤, 두 구간의 최소치 중 더 작은 값을 취한다.

각 노드의 처리 시간은 상수시간이고, 총 노드의 수는 n*4를 넘지 않는다.

따라서 초기화 과정은 O(n)의 시간 복잡도를 가진다.

 

구간 트리의 질의 처리 (query)

 

query(l, r, node, nl, nr)

 = node가 표현하는 범위 [nl, nr] 와 최소치를 찾기 위한 구간[l, r]의 교집합의 최소 원소를 리턴.

 

 

[i, j] 의 구간 => query(i, j, 1, 0, n-1)

 

- 교집합이 공집합인 경우: 반환값 없음. 무한대값을 반환.

- 교집합이 [nl, nr]인 경우: [l, r]이 완전히 포함하는 경우, 미리 전처리한 값을 반환.

- 그외 경우: 두개의 자손 노드를 조사하여 두 값중 최소 반환.

 

struct RMQ {
    int n;
    vector<int> rangeMin;
    RMQ(const vector<int>& array) {
        n = array.size();
        rangeMin.resize(n*4);
        init(array, 0, n-1, 1);
    }
    int init(const vector<int>& array, int left, int right, int node) {
        if(left == right)
            return rangeMin[node] = array[left];
        int mid = (left + right) / 2;
        int leftMin = init(array, left, mid, node*2);
        int rightMin = init(array, mid + 1, right, node*2 + 1);
        return rangeMin[node] = min(leftMin, rightMin);
    }
    int query(int left, int right, int node, int nodeLeft, int nodeRight) {
        if( right < nodeLeft || nodeRight < left) return INT_MAX;
        if( left <= nodeLeft && nodeRight <= right) return rangeMin[node];
        int mid = (nodeLeft + nodeRight)/2;
        return min(query(left, right, node*2, nodeLeft, mid),
                   query(left, right, node*2+1, mid+1, nodeRight));
     }
    int query(int left, int right) {
        return query(left, right, 1, 0, n-1);
    }
};

 

query함수는 구간이 겹치지 않거나 완전히 포함하거나 곧장 함수를 종료시키기 때문에 모든 노드를 탐색하지 않는다.

 

원하는 구간이 나올때 까지 절반씩 탐색하고, 최악의 경우 트리의 바닥까지 최대 두번만 탐색한다.

(왼쪽 오른쪽 두번)

그러므로 O(lgn)의 시간 복잡도를 가진다.

 

 

구간 트리의 갱신(update)

배열의 값이 변경되면 그 값이 포함된 구간만 변경하면된다, 값은 리프에 있으며 총 높이가 lgn이므로 

lgn 시간에 수행된다.

 

업데이트 과정은 query 와 init 연산을 합친것처럼 구현된다.

int update(int index, int newValue, int node, int nodeLeft, int nodeRight) {
    if(index < nodeLeft || nodeRight < index) return rangeMin[node];
    if(nodeLeft == nodeRight) return rangeMin[node] = newValue;
    int mid = (nodeLeft + nodeRight) /2;
    return rangeMin[node] = min(
    	update(index, newValue, node*2, nodeLeft, mid), 
        update(index, newValue, node*2+1, mid + 1, nodeRight));
}
int update(int index, int newValue) {
    return update(index, newValue, 1, 0, n-1);
}

각 노드에 대해 위치등을 저장해 두지 않았기 때문에 루트에서부터 탐색해나간다.(시간복잡도는 동일하다,)

 

 

3. 펜윅 트리(Fenwick Tree)(binary indexed tree)

 

구간 트리로 가장 흔히 사용되는 연산은 구간 합을 빠르게 하느 것이다.

이는 앞에서 다루었던 부분합 배열보다 배열의 원소를 갱신하는데 더 효율적이다.

(부분 합은 A[0]으로 고정된 구간 합)

 

 

 

펜윅 트리의 구조

 

펜윅 트리는 이런 연산을 할 수 있는 더 효율적인 트리 구조이다.

 

펜윅 트리의 핵심 아이디어는 구간 합 대신 부분합 만을 빠르게 계산할 수 있는 자료 구조를 만들어도 

구간 합을 계산할 수 있다는 것이다.

 

psum[pos] = A[0] + A[1] .. A[pos] => 구간합: psum[j] - psum[i-1]

 

 

구간 합을 담는 구간 트리를 만들게 되면 쓸모 없는 정보들 까지 저장된다. 아래 표는 필요 없는 구간을 지워 펜윅트리를 만든 모양새이다.

0, 15
0, 7
0,3					8,11
0, 1			4, 5		8, 9			12, 13
0		2	4	6	8		10	12	14

왼쪽 구간과 오른쪽 구간을 같이 사용할 경우 부모노드와 동일한 구간이 나온다.

오른쪽 구간은 또한 부분합을 이용하여 얻어 낼 수 있다.

그러므로 오른쪽 구간은 필요가 없어 따로 저장할 필요 없다.

 

 

필요 없는 구간을 제거한 펜윅트리의 구간의 개수는 n개이다.

(전체 구간들의 오른쪽 원소가 모두 다르다)

 

 

 

펜윅 트리에서의 구간 합 계산

구간의 총 개수는 n개이므로 일차원 배열 하나에 각 구간의 합을 저장할 수 있다.

 

오른쪽 원소가 모두 다르고, 0~N-1 의 값을 가지고 있기 때문에 이를 배열의 인덱스로 삼을 수 있으므로

다음과 같이 표현 할 수 있다.

 

tree[i] = 오른쪽 끝 위치가 A[i]인 구간의 합.

 

psum[pos]: tree[pos]와 왼쪽에서 이어지는 것들의 합

 (O(lgn) 개의 구간 합만 필요)

 

문제는 이어지는 것들을 찾는 것이다.

 

펜윅 트리는 각 숫자의 이진수 표현을 이용하여 다음으로 더해야 할 구간을 찾는다.

 

배열 A와 tree의 모든 원소의 인덱스에 1을 더해보자.

 

그러면 더해야 할 구간 합들은 다음과 같이 표를 보면 특정한 규칙이 있다는 것을 알 수 있다..

 

16: 10000
8: 1000
4: 100					12: 1100
2:10			6:110		10: 1010			14: 1110
1:1		3:11	5:101	7: 111	9: 1001		11:1011	13:1101	15:1111

pos의 최소 비트를 없애면 다음으로 더해야할 구간을 찾을 수 있다는 규칙을 찾을 수 있다.

 

13: 1101 -> 1100 -> 1000

6: 110->100

5: 101->100

 

특정 pos를 포함하는 구간에도 규칙이있다.

 

1: 1 -> 10 -> 100 -> 1000 -> 10000

3: 11-> 100 -> 1000 -> 10000

10: 1010-> 1100 -> 10000

 

특정 pos를 포함하는 구간은 최소 비트에 1 을 더해나가면 결국 루트에 도달하는 것을 알 수 있으며

이는 배열의 값을 변경하고, 구간합을 업데이트 시킬때 사용된다.

 

 

펜윅트리의 구현

책에서는 비트 마스크를 이용하여 구현하였다.

sum 과 add 연산 두개는 모두 밑에서 부터 루트까지 연산이 수행된다.

따라서 트리의 높이에 지배되고 O(lgn)만에 수행된다.

struct FenwickTree {
    vector<int> tree;
    FenwickTree(int n) : tree(n+1) {}
    int sum(int pos) {
        ++pos;
        int ret = 0;
        while(pos>0) {
            ret += tree[pos];
            pos&=(pos-1);
        }
        return ret;
    }
    void add(int pos, int val) {
        ++pos;
        while(pos < tree.size()) {
            tree[pos] += val;
            pos += (pos & -pos);
        }
    }
};

 

 

 

- 알고리즘 문제해결전략 737p