Segment Tree

Segment Tree

 

  구간 트리는 자료를 이진트리의 형태로 조직화한 트리로서 동적인 구간 질의에 효율적으로 답하기 위한 자료구조이다. 여기서 동적이라는 말은 자료를 갱신해 가면서 질의에 답할 수 있어야 한다는 뜻이다. 구간질의란 데이터가 저장된 자료구조(여기서는 선형적 예를 들어 배열을 다룰 것이다.)에서 임의의 구간이 주어 졌을때 그 구간에 대한 질의를 뜻한다. 예를 들어 구간 최소질의(RMQ, Range Minimum Query)가 이해 해당된다. RMQ는 해당되는 칸의 최솟값의 인덱스를 구하는 문제이다. 다시말해 구간트리를 이용하여 이같은 문제를 효율적으로 해결할 수 있다는 것이다.

  구간트리는 이진 트리의 형태로서 모든 노드의 자식은 둘 이하이다. 구간 트리는 각 노드가 해당되는 구간에대한 질의의 값들을 저장한다. 노드에 해당되는 구간은 다음과 같다.

 예를 들어 길이가 N인 배열이 주어졌다고 가정하고 해당 배열에 대한 동적인 구간질의의 값들을 구간트리 T가 저장한다고 가장하자.

1. T의 루트는 해당 배열 전체 구간 즉, 0 ~ N - 1 까지의 범위에 대한 질의의 결과값을 저장한다. 

2. 임의의 노드가 LEFT ~ RIGHT 구간에 대한 질의값을 저장하고 있다. 이때 중앙값 MID(MID = (LEFT + RIGHT) / 2)를 정의한다. 그러면 왼쪽 노드에 할당되는 구간은 LEFT ~ MID, 오른쪽 노드에 할당되는 구간은 MID + 1 ~ RIGHT 이다.

 

SegmentTree 구현

 

  앞서 구간트리는 이진 트리 형태임을 언급했다. 이때 구현될 이진트리는 각 노드를 클래스나 구조체로 정의하고 이를 포인터로 잊는 식으로 구현하지 않고 heap과 같이 배열을 이용하여 구현된다. 루트는 배열의 1번 인덱스에 저장된다. 임의의 노드 i의 왼쪽자식은 2 * i 이고, 오른쪽 자식은 2 * i + 1 이다. 그리고 부모노드의 인덱스는 i / 2가 된다. 구간트리를 통해 RMQ 문제를 푼다고 가정해보자. 임의의 구간이 주어지면 해당 구간의 최솟값을 반환해야 된다. 우리는 이 값을 구하기 위하여 구간트리의 루트부터 탐색을 시작한다.

1. 현재 탐색되는 노드의 구간이 문제에서 주어진 구간의 바깥에 해당된다면 (즉 겹치는 구간이 없다면) 해당 노드의 값은 문제를 해결하는데 있어서 필요가 없다.

2. 현재 탐색되는 노드의 구간이 문제에서 주어진 구간의 안쪽에 (포함된거나 같다면) 해당 노드의 질의 값을 반환한다.

3. 현재 노드의 구간과 주어진 구간이 1.과 2. 에 속하지 않는다면 즉, 두구간이 겹치는데 현재 노드의 구간이 주어진 구간 안쪽에 있는 것이 아니라면 우리는 현재 구간을 반으로 나누나 각 각의 구간에 대한 질의값을 재귀 적으로 구한다.

 

SegmentTree's ADT(Abstract Data Type)

 

SegmentTree(const vi &_A) = SegmentTree 생성자

int rmq(int i, int j) = 해당 배열의 구간 i ~ j에 해당되는 최솟값의 인덱스를 반환한다.

int update(int i, int k) = 동적구간 질의를 위한 코드. A[i]의 값이 k로 변경 되었을때 구간트리를 수정한다.

 

Code of SegmentTree

 

class SegmetTree{

private:    vi st, A;    //vi는 vector<int>

int n;

int left(int i) {    return i << 1;    }

int right(int i) {    return (i << 1) + 1;    }

void build(int P, int L, int R) {

if(L == R)

st[P] = L;

else {

int mid = (L + R) / 2;

build(left(P), L, mid);

build(right(P). mid + 1, R);

int p1 = st[left(p)], p2 = st[right(p)];

st[P] = (A[p1] < A[p2]) ? p1 : p2;

}    }

int rmq(int P, int L, int R, int i, int j) {

if(R < i || j < L)    return -1;    //현재 구간이 질의 구간 바깥쪽

if(i <= L && R <= j)    return st[p];    //현재 구간이 질의 구간 안쪽

//구간이 안쪽도 바깥쪽도 아닌 두구간이 겹쳐질 경우

int mid = (L + R) / 2;

int x = rmq(left(P), L, mid), y  = rmq(right(P), mid + 1, R);    //분할 정복

if(x == -1)    return y;

if(y == -1)    return x;

return (A[y] < A[x] ? y : x);    }

int update(int P, int L, int R, int i, int k) {

if(L == R) {

if(L == i)

A[L] = k;

return st[P];

}

if(i < L || R < i)

return st[P];

int mid = (L + R) / 2;

int p1 = update(left(P), L, mid, i, k), p2 = update(right(P), mid +1 ,R, i, k);

return st[P] = (A[p1] < A[p2] ? p1: p2);    }

public:

SegmentTree(const vi &_A){

A = _A; n = A.size(); st.resize(4 * n); 

build(1, 0, n - 1);    }

int rmq(int i, int j) {    return rmq(1, 0, n - 1, i, j);    }

int update(int i, int k)    {  

return update(1, 0, n - 1, i, k);

}    };