세그먼트 트리(Segment Tree)

 

 

 

Overview

트리 자료구조는 데이터를 효율적으로 저장하고, 빠른 시간에 탐색, 수정 및 추가 삭제 연산을 진행할 수 있도록 도와줍니다. 구간 트리(Segment Tree)는 이 트리 구조의 이점을 살려서 특정 구간에서의 최대, 최소 값등을 빠르게 구할 수 있도록 합니다.

 

구간 트리는 특히 일차원 배열의 특정 구간에 대한 질문들(최대, 최소값 등)을 빠르게 대답하는 데에 주로 사용합니다. 예를 들어, 일차원 배열의 특정 구간에서 최대인 값을 찾기 위해서는 특정 구간을 일일이 순회하면서 최소값을 찾아야 했습니다. 하지만, 구간 트리를 이용하면 특정 구간의 최대값을 미리 전처리해서 부모 노드에 저장하는 방식을 취하기 때문에 (일종의 다이나믹 프로그래밍 방법이라고도 할 수 있습니다.) 훨씬 더 빠른 시간에 탐색이 가능한 것입니다.

 

Definition

 

앞서 설명한 것과 같이 세그먼트 트리는 자식 구간의 정보를 부모 노드에 기록하는 방식을 취합니다. 아래의 그림을 보면, 1, 3, 5, 7, 9, 11번 노드의 구간 정보를 저장하기 위해서 나머지 노드가 사용되고 있는 것을 볼 수 있습니다. 이 세그먼트 트리가 저장하는 구간 정보가 최소값일 경우, 4번 노드는 1, 3번 노드 중의 최솟값을, 16번 노드는 7, 9번 노드 중의 최솟값을 저장합니다. 마찬가지로 9번 노드는 1, 3, 5번 노드의 최솟값을 저장하고, 이런식으로 제일 마지막 36번 노드는 모든 노드의 최솟값을 저장하게 되는 것입니다.

 

 

 

image from https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/

 

 

대부분의 트리 자료구조가 그렇듯이, 세그먼트 트리도 초기화 하고, 질의하고(query), 값을 업데이트 하는데 있어서 재귀 함수를 사용합니다. 재귀함수를 이용할 경우 세그먼트 트리를 간단하게 구현할 수 있습니다.

 

 

초기화(Init)

 long init(int arr[], int left, int right, int node) {
    
    if (left == right) return segArr[node] = arr[left]; // leaf node case;
    int mid = (left+right)/2;
    return segArr[node] = Math.min(init(arr, left, mid, node*2), init(arr, mid+1, right, node*2+1));

}

루트 노드로부터 시작해서 왼쪽, 오른쪽 자식 노드 중의 최솟값을 값으로 갖도록 작성합니다. 왼쪽 오른쪽 자식 노드의 최솟값을 구하기 위해서는 자식의 자식 노드들로부터의 최솟값을 구해야 하므로 간단하게 함수를 작성할 수 있습니다.

 

 

 

질의(Query)

long query(int sIdx, int eIdx, int node, int nodeLeft, int nodeRight) {
    
    if (sIdx > nodeRight || eIdx < nodeLeft) return Integer.MAX_VALUE;
    if (sIdx <= nodeLeft && eIdx >= nodeRight) return segArr[node];
    int mid = (nodeLeft + nodeRight) / 2;
    return Math.min(query(sIdx, eIdx, node*2, nodeLeft, mid), query(sIdx, eIdx, node*2 +1, mid+1, nodeRight));

}

질의를 작성하는 부분도 초기화와 거의 비슷합니다. 찾으려는 구간이 현재 구간안에 포함될 때까지 재귀함수를 통해 작성해 주면 됩니다. 현재 구간이 찾으려는 구간보다 클 경우에는 마찬가지로 구간을 쪼개어 각각의 최솟값을 구한다음에, 그 최솟값들의 최솟값을 구하면 됩니다. 

 

 

소스 코드(JAVA)

구간의 최소값을 구하는 세그먼트 트리를 작성한 코드 입니다. 

class MinSegTree {

    long segArr[];

    MinSegTree(int[] arr, int arrSize) {
    
        this.segArr = new long[arrSize * 4];
        Arrays.fill(segArr, Integer.MAX_VALUE);
        init(arr, 0, arrSize-1, 1);
        
    }

    long init(int arr[], int left, int right, int node) {
    
        if (left == right) return segArr[node] = arr[left]; // leaf node case;
        int mid = (left+right)/2;
        return segArr[node] = Math.min(init(arr, left, mid, node*2), init(arr, mid+1, right, node*2+1));
    
    }

    long query(int sIdx, int eIdx, int node, int nodeLeft, int nodeRight) {
    
        if (sIdx > nodeRight || eIdx < nodeLeft) return Integer.MAX_VALUE;
        if (sIdx <= nodeLeft && eIdx >= nodeRight) return segArr[node];
        int mid = (nodeLeft + nodeRight) / 2;
        return Math.min(query(sIdx, eIdx, node*2, nodeLeft, mid), query(sIdx, eIdx, node*2 +1, mid+1, nodeRight));
    
    }