[Algorithm] 구간트리

구간트리

구간 트리는 일차원 배열의 특정 구간에 대한 질의를 빠르게 대답하는데 사용된다.

예를 들어 어떤 숫자들이 주어진다고 가정해보자.

S = {1, 2, 1, 2, 3, 1, 4, 2, 2}

이 숫자들에 특정 구간에 대한 질의가 들어온다고 생각해보자.

예를들면 [2, 4] 구간의 최소값은 1이고, [6, 8]구간의 최소값은 2이다.

물론 이 처리를 위해 순회를 하며 최소값을 찾을 수 있다. 하지만 이 방법은 O(N)의 수행시간을 갖는다.

만약 이러한 질의가 무수히 많이 들어온다면 어떨까?

기존의 방법대로라면 쿼리의 개수가 Q라고 했을 때, O(Q x N)의 수행시간을 갖게 될 것이다.

하지만 구간트리는 하나의 쿼리를 O(logN) 시간에 수행할 수 있고, 모든 쿼리에 대해서는 O(QlogN) 시간에 동작한다.

 

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

트리의 루트는 [0, N - 1] 구간을 표현하고, 루트의 left, right 자식들은 각각 [0, N / 2], [N / 2 + 1, N - 1] 구간을 표현한다. 이렇게 구간 내의 원소가 하나일 때까지 반으로 쪼개며 모든 구간들을 표현하는 이진트리를 구성한다.

이 그림은 각 노드가 표현하는 구간들을 보여준다. 맨 위 0번 노드가 루트이고 [0, 14] 구간을 표현한다.

양쪽 아래는 루트의 두 자식 노드들이 표현하는 구간들을 나타낸다. 이때 구간 트리는 노드마다 해당 구간에 대한 계산 결과를 저장해둔다. 즉 모든 구간 조각들에 대한 계산결과들을 각 노드들이 들고 있는 형태이다.

이런 전처리 과정을 수행해 두면, 어떤 구간 [i, j]가 주어지더라도 이 구간을 구간 트리의 노드에 포함된 구간의 합집합으로 표현할 수 있다. 예를 들면 위 배열에서 [6, 12] 구간은 진하게 색칠된 세 구간 [6, 7], [8, 11], [12, 12]의 합집합으로 표현이 가능하다.

 

이제 각 구간의 최소값을 찾는 구간트리를 구현해보자.

일단 트리를 저장할 자료구조를 생각해봐야 한다.

위 그림을 보면 알 수 있듯이, 구간트리는 거의 꽉 찬 이진트리이다.

이러한 꽉 찬 이진트리를 표현하기 위해서는 굳이 노드 링크보다는 배열을 사용하는것이,

메모리, 성능 측면에서 효율적이다.

루트 노드를 배열의 1번 원소로 두고, i번째 노드의 두 자식 노드는 (2 * i)과 (2 * i + 1)번 노드로 표현할 수 있다.

 

배열의 크기는 n이 2의 거듭제곱이라면 2 * n의 크기로 잡으면 되겠지만,

n의 크기가 거듭제곱이 아닌 경우, 예를들면 n이 6인 경우는 인덱스가 12를 초과하게 된다.

이런 경우까지 모두 포함시키기 위해 4 * n의 크기로 잡는다. (메모리는 조금 낭비될 것이다.)

다음 그림은 n이 6인 경우의 구간트리의 모습이다. (노드번호, [범위])

 

 

구간트리 연산

초기화 (Init)

구간트리의 초기화 단계에서는 배열의 모든 원소들에 대해,

루트로부터의 모든 구간에 대한 답(최소값)을 미리 계산해둔다.

그러기 위해서는 각 구간에 대한 최소값을 저장할 배열을 하나 만들어 두어야 할 것이다.

// tree는 구간들을 표현하고, 각 구간의 최소값을 저장한다
vector<int> tree;

 

이 작업은 루트로부터 리프까지 모든 노드들을 재귀적으로 거슬러 내려가도록 구현할 수 있다.

어떤 노드가 표현하는 구간에 대한 최소값은, 자신의 두 자식 노드들이 표현하는 각각의 구간에 대한 두 개의 최소값들 중 더 작은 값으로 저장하도록 한다.

구간트리의 초기화 함수 인자는 다음과 같이 구성한다.

구간트리의 재료가 될 원소들을 위한 v,

재귀적으로 각 노드 번호를 표현하기 위한 node,

재귀적으로 노드의 구간을 표현하기 위한 from, to 를 인자로 잡는다.

그리고 분할정복을 통해 모든 구간에 대한 최소값을 tree에 저장한다.

    // 구간트리의 초기화
    int Init(const vector<int>& v, int node, int from, int to)
    {
        if (from == to)
            return tree[node] = v[from];

        // 각 구간들의 최소값을 저장
        int mid = (from + to) / 2;
        int left_min = Init(v, node * 2, from, mid);
        int right_min = Init(v, node * 2 + 1, mid + 1, to);
        return tree[node] = min(left_min, right_min);
    }

 

질의 (Query)

각 구간 조각들에 대한 최소값들을 저장하였다면, 이제 임의의 질의 구간에 대한 최소치를 구할 수 있다.

이것을 구간트리에서의 질의(Query)라고 부른다. 이 연산은 구간트리의 순회를 통해 쉽게 구현할 수 있다.

질의 함수는 다음과 같은 인자들을 갖도록 한다.

재귀적으로 각 노드 번호를 표현하기 위한 node,

재귀적으로 노드의 구간을 표현하기 위한 from, to

쿼리 구간을 표현하기 위한 qfrom, qto 를 인자로 잡는다.

int Query(int node, int qfrom, int qto, int from, int to)

 

이제 쿼리 구간과, 경계구간이 어떤 형태로 겹쳐지느냐에 따라 달라진다.

다음과 같이 상황을 나눌 수 있다.

 

1. 쿼리구간과, 경계구간이 겹치지 않는 경우

두 구간이 서로 겹치지 않기 때문에, 이 상황에서 Query 함수의 반환값은 존재하지 않는다.

반환값이 무시되도록 아주 큰 값을 반환하도록 한다.

 

2. 경계구간이 쿼리구간에 포함되는 경우

[qfrom, qto]가 [from, to]를 완전히 포함하는 경우이다.

이 경우, [from, to] 구간의 최소값인 tree[node]를 반환한다.

 

3. 그 외의 경우 (경계구간과 쿼리구간이 겹치지만 부분만 겹치는 경우)

두 개의 자식에 대해 구간을 나누어 재귀호출한 뒤, 두 노드로부터 얻은 각각의 최소값들 중 더 최소인 값을 반환한다.

    // 인터페이스 함수
    // query range [qfrom, qto]
    int Query(int qfrom, int qto)
    {
        return Query(1, qfrom, qto, 0, N - 1);
    }

    // 질의된 구간 내의 최소값을 구한다.
    // query range [qfrom, qto]
    // boundary range [from, to]
    int Query(int node, int qfrom, int qto, int from, int to)
    {
        // 구간이 겹치지 않는다면 매우 큰 값을 리턴 (이 값은 무시됨)
        if (qto < from || to < qfrom)
            return numeric_limits<int>::max();
        
        // 쿼리 구간에 분할 구간이 완전히 겹쳐진다면, 해당 구간의 최소값을 반환
        if (qfrom <= from && to <= qto)
            return tree[node];
        
        // 왼쪽 구간트리의 최소값, 오른쪽 구간트리의 최소값 중 최소값
        int mid = (from + to) / 2;
        int left_min = Query(2 * node, qfrom, qto, from, mid);
        int right_min = Query(2 * node + 1, qfrom, qto, mid + 1, to);
        return min(left_min, right_min);
    }

 

 

수정 (Update)

전처리를 통해 구간 트리를 생성한 다음에 원래 배열의 값이 바뀌는 경우는 어떻게 해야 할까?

처음부터 다시 구간 트리를 생성하는것은 너무 비용이 크다.

값이 하나 바뀐 상황에 대해서는 빠르게 구간트리를 갱신할 수 있다.

원래 배열의 index 위치의 값이 새로운 값으로 바뀌었다고 가정해 보자. 

이 위치를 포함하는 구간트리의 노드들은 O(logN) 개 존재할 것이다.

이들만 재계산한다면 O(logN) 시간에 구간트리를 갱신할 수 있다.

 

수정 함수는 다음과 같은 인자들을 갖도록 한다.

재귀적으로 각 노드 번호를 표현하기 위한 node,

재귀적으로 노드의 구간을 표현하기 위한 from, to

수정될 데이터의 주소와, 값을 위한 index, newvalue

    // 구간트리의 특정 index 위치 값을 새로운 값으로 갱신한다.
    int Update(int node, int index, int newvalue, int from, int to)
    {
        // index가 구간에 포함되지 않는다면, 원래 값을 리턴 (이 값은 무시됨)
        if (index < from || to < index)
            return tree[node];

        // 트리의 리프에 도달 시, 값 갱신
        if (from == to)
            return tree[node] = newvalue;

        // 이 위치에 진입했다는 것은 구간에 index가 포함된다는 의미이다.
        // 재귀적으로 이 작업을 반복하고, 얻은 값을 통해 현재 구간을 갱신한다.
        int mid = (from + to) / 2;
        int left_min = Update(2 * node, index, newvalue, from, mid);
        int right_min = Update(2 * node + 1, index, newvalue, mid + 1, to);
        return tree[node] = min(left_min, right_min);
    }

 

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/SegmentTree/1-Min-SegmentTree.cpp

insooneelife/AlgorithmTutorial

 

 

합을 표현하는 구간트리

예제 문제

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

 

구간갱신