Segment Tree

Segment Tree

구간 트리(Segment Tree)는 저장된 자료의 특정 구간 질의를 빠르게 대답하기 위해 저장된 자료를 전처리한 트리를 말한다. 흔히 구간 트리는 일차원 배열의 특정 구간 질의를 빠르게 대답하는데 사용된다. 예를 들어 [1, 7, 5, 3, 2] 라는 일차원 배열이 있을 때 [1, 2] 구간의 최소치를 찾는 연산을 해야 한다. 이를 연산하는 간단한 방법은 구간의 시작부터 끝까지 순회하면서 최소치를 찾으면 되며 시간 복잡도는 O(N)이 된다. 반면 구간 트리를 한 번 만들어두면 위 연산을 O(log N)으로 할 수 있다.

 

구간 트리의 핵심 아이디어는 배열 구간에 대한 이진 트리를 만드는 것이다. 구간 트리의 노드는 구간을 표현한다. 루트 노드는 항상 배열의 전체 구간 [0, n-1]을 표현하며 왼쪽 자식 노드와 오른쪽 자식 노드는 각각 루트 노드 구간의 왼쪽 반과 오른쪽 반을 표현한다. 길이가 1인 구간을 표현하는 노드는 리프 노드가 된다.

구간 트리

구간 트리의 각 노드는 구간에 대한 연산 결과를 저장한다. 예를 들어 구간의 최소치를 구하는 구간 트리의 노드는 해당 노드가 표현하고 있는 구간의 최소치를 저장하고 있다.

 

위 그림에서 [0, 14] 내의 어떤 구간이 들어와도 노드가 표현하고 있는 구간들의 합집합으로 표현할 수 있다. 예를 들어 [6, 12] 구간은 위 그림에서 칠해진 세 구간 [6, 7], [8, 11], [12]의 합집합으로 표현할 수 있다. 이들 세 구간의 최소치가 [6, 12] 구간의 최소치가 된다. 따라서 어떤 구간에 대한 질의가 들어오더라도 노드의 합집합 연산을 통해 응답할 수 있다. 이 과정을 O(log N)에 수행한다.

구간 트리 구현

구간의 최소치를 구하는 구간 트리를 구현해 보자.

 

1. 구간 트리 표현

구간 트리는 거의 꽉 찬 이진 트리이다. 이렇게 꽉 찬 이진 트리는 이진 검색 트리처럼 포인터로 연결된 객체로 표현하기보다 힙의 구현처럼 배열로 표현하는 것이 더 메모리를 절약할 수 있다. 루트 노드를 배열의 0번 원소로 할때, i번 노드의 왼쪽 자식 노드, 오른쪽 자식 노드는 각각 2 * i + 1와 2 * i + 2번 원소이다. 이 배열의 길이는 얼마나 되어야 할까? 구간의 최대 길이가 n이고 n이 2의 거듭제곱이라면 이 배열의 길이는 2n - 1이면 된다. 하지만 n이 2의 거듭제곱이 아닐 수도 있기에 n을 가장 가까운 2의 제곱으로 올림한뒤 2를 곱해줘야 한다. 이것이 귀찮으면 4n의 크기로 만들면 된다.

 

노드가 가지는 값은 구간의 계산 결괏값이다. 구간의 범위를 따로 저장하지 않는다. 루트 노드에서 자식 노드의 구간을 계산할 수 있기 때문이다.

 

 

2. 구간 트리 초기화

class SegmentTree {
    int n;
    int[] nodeArr;

    public SegmentTree(int[] arr) {
        n = arr.length;
        nodeArr = new int[n * 4];
        init(0, 0, n-1, arr);
    }
    
    private int merge(int nodeA, int nodeB) {
        return Math.min(nodeA, nodeB);
    }
    
    private int init(int node, int nodeLeft, int nodeRight, int[] arr) {
        if(nodeLeft == nodeRight) return nodeArr[node] = arr[nodeLeft];

        int mid = (nodeLeft + nodeRight) / 2;
        int LNode = init(node * 2 + 1, nodeLeft, mid, arr);
        int RNode = init(node * 2 + 2, mid + 1, nodeRight, arr);
        return nodeArr[node] = merge(LNode, RNode);
    }
}

init 메서드는 nodeLeft, nodeRight 구간을 표현하는 노드에 연산 결과를 저장하고 해당 노드를 반환한다. 두 자식 노드를 합치는 메서드(merge)로 연산이 수행된다.

 

루트에 대한 init 메서드가 수행되면 트리의 각 노드는 해당 구간에 대한 연산 결과를 갖게 된다. init 메서드의 시간 복잡도는 O(N)이 된다.

 

 

3. 질의 처리

private int query(int node, int nodeLeft, int nodeRight, int queryLeft, int queryRight) {
    //두 구간의 교집합이 없는 경우
    if(queryRight < nodeLeft || nodeRight < queryLeft) return Integer.MAX_VALUE;

    //queryLeft..queryRight 구간이 nodeLeft..nodeRight 구간을 완전히 포함하는 경우
    if(queryLeft <= nodeLeft && nodeRight <= queryRight) return nodeArr[node];

    int mid = (nodeLeft + nodeRight) / 2;
    int LNode = query(node * 2 + 1, nodeLeft, mid, queryLeft, queryRight);
    int RNode = query(node * 2 + 2, mid + 1, nodeRight, queryLeft, queryRight);
    return merge(LNode, RNode);
}

public int query(int queryLeft, int queryRight) {
    return query(0, 0, n-1, queryLeft, queryRight);
}

query 메서드는 질의가 들어온 queryLeft..queryRight 구간과 노드가 표현하고 있는 nodeLeft..nodeRight 구간의 교집합 연산 결과를 반환한다. 교집합의 경우의 수는 아래와 같다.

• 두 구간의 교집합이 공집합인 경우 (기저 조건) : 교집합이 없으므로, 연산 결과도 없다. 반환값이 무시되도록 특정 값을 리턴한다.
• queryLeft..queryRight 구간이 nodeLeft..nodeRight 구간을 완전히 포함하는 경우 (기저 조건) : nodeLeft..nodeRight를 표현하는 노드의 연산 결과를 리턴한다.
• 그 외 경우 : 자식 노드에 query 메서드를 수행하고 반환된 값을 합친다.

그 외 모든 경우에서 두 자식 노드에 재귀 함수를 호출하니 O(N)의 성능으로 동작한다고 생각할 수 있다. 아래 그림을 보자.

그림은 노드가 가지는 교집합 상태의 모든 경우(A, B, C, D , E)를 보여준다. 회색으로 칠해진 부분이 교집합이다. 구간이 다 흰색으로 칠해진 경우, 다 회색으로 칠해진 경우 등 기저 조건 경우는 제외했다. 아래 (1)이라 쓰여있는 부분은 기저 조건에 해당하는 집합이므로 해당 집합에 query 메서드를 수행하면 바로 반환된다는 걸 알 수 있다.

 

이 그림에서 중요한 점은 노드가 A 경우를 가질 때만 두 가지 경우로 분기된다는 점이다. (어느 한쪽도 바로 반환되지 않는다.) 하지만 분기되더라도 A 경우가 다시 발생하지 않으며 C, D는 한 가지 경우로 분기되고 E는 분기되지 않는다. 따라서 두 가지 경우로 계속 분기되지 않는다. 정리하면 A, B 경우는 한 번만 발생할 수 있으며 루트에서 A or B 경우가 발생할 때만 A 경우가 발생한다. 최악의 경우 A에서 분기된 두 개의 (C or D) 경우가 반복되는 경우(리프 노드를 두 번 가는 경우)이므로 query의 시간 복잡도는 O(log N)이 된다.

 

4. 구간 트리 갱신

원본 배열의 값이 바뀌면 새 구간 트리를 만들어야 하지만 값이 하나 바뀔 때는 구간 트리를 빠른 시간에 갱신할 수 있다.

private int update(int node, int nodeLeft, int nodeRight, int updateIndex, int newValue) {
    //updateIndex가 nodeLeft..nodeRight 구간에 포함하지 않는 경우
    if(updateIndex < nodeLeft || nodeRight < updateIndex) return nodeArr[node];

    //리프 노드까지 내려온 경우
    if(nodeLeft == nodeRight) return nodeArr[node] = newValue;

    int mid = (nodeLeft + nodeRight) / 2;
    int LNode = update(node * 2 + 1, nodeLeft, mid, updateIndex, newValue);
    int RNode = update(node * 2 + 2, mid + 1, nodeRight, updateIndex, newValue);
    return nodeArr[node] = merge(LNode, RNode);
}

update 메서드는 updateIndex 위치의 값이 newValue로 바뀔 때, 노드가 표현하는 구간(nodeLeft..nodeRight)이 updateIndex를 포함하는 경우 해당 노드의 연산 결과를 업데이트 하는 메서드이다.

 

구간 트리 갱신도 두 개의 자식 노드에 재귀 함수를 호출하니 O(N)으로 생각할 수 있지만 자식 노드 중 하나는 바로 반환되기 때문에 한 가지 경우로만 분기된다. 따라서 시간 복잡도는 O(log N)이 된다.