[자료구조] 세그먼트 트리

세그먼트 트리

• 구간 쿼리(Query)와 업데이트를 효율적으로 처리하기 위한 트리
• 특정 구간의 합, 최소값, 최대값 등을 빠르게 계산. O(logN)
• 범위 합 구하기, 구간 최소값/최대값 구하기

누적합의 경우 합계를 구할 때만 사용할 수 있고, 특정 값이 업데이트될 경우 나머지 값들도 모두 업데이트가 되어야 함.

세그먼트 트리의 경우 구간내의 다양한 값들을 구할 수 있고, 업데이트될 경우 몇개의 수만 업데이트하면 됨.

 

즉, 구간내의 다양한 값(최대값, 최소값)과 업데이트가 빈번하게 일어날 경우, 누적합이 아닌 세그먼트 트리 사용

---

세그먼트 트리 초기화

배열에 대해 세그먼트 트리를 형성하기 위해서는 이분탐색과 비슷한 느낌으로 2개씩의 합을 구하고, 구한 합에 대해 또 2개씩 합을 구하며 최종 한 개의 합까지 구합니다.

만약 2개로 묶이지 않는 경우 0이라 생각하고 합을 구합니다.

아래의 그림과 같은 방식으로 진행됩니다.

위의형태에 대해서 81을 Root노드로 이진트리를 형성하면 입력에 대한 세그먼트 트리를 완성시킬 수 있습니다.

---

구간합 구하기

4번쨰 원소(7)부터 9번째 원소(17)까지의 구간합을 구하는 경우 다음과 같은 방식으로 진행됩니다.

최초 81은 범위밖의 원소를 포함하고 있기에 이분탐색처럼 두 부분으로 나누어 범위를 줄여나갑니다.

64에서 16, 48로 범위를 줄였을 때 다음과 같은 두 가지 상황이 있습니다.

1. 16의 경우 아직 범위 밖의 값이 존재하기에 범위를 더 줄입니다.
2. 48의 경우 5,6,7,8 원소로 범위 밖의 값이 존재하지 않기에 탐색을 종료합니다.

이렇게 원소의 범위에 맞게 끝까지 탐색하게 될 경우, 최종적으로 구간합을 구할 수 있습니다.

---

값 업데이트

사실 단순하게 구간합만을 구하는 것이라면, 누적합 또는 투포인터가 더욱 효율적입니다.

그러나 원소값의 업데이트가 빈번하게 일어날 경우 바뀐 원소에 대한 누적합을 계속 탐색해야하기에 시간복잡도가 크게 올라가게 됩니다.

세그먼트 트리를 사용할 경우 효율적으로 값의 업데이트를 적용하고, 구간합 탐색을 수행할 수 있습니다.

위 그림에서 첫번째 원소(1)의 값이 10으로 변경되었을 때, 몇 번의 연산이 수행되는지 그림으로 보겠습니다.

해당 원소를 범위에 포함하고 있는 노드의 값을 변경하면 됨으로, 2/N번의 연산으로 업데이트를 적용할 수 있는 것을 확인할 수 있습니다.

위 그림을 트리 형태로 간단하게 나타내면 다음과 같습니다.

---

시간복잡도 계산

1. 세그먼트 트리 초기화
   1. 트리의 높이는 logN == h
   2. 배열의 크기는 2^h+1
   3. 모든 노드가 정확히 한 번씩 처리 (노드 개수 : 2N -1)
   4. 최종 시간복잡도 O(N)
2. 구간합 계산
   1. 이분 탐색과 비슷한 방식으로 O(logN) 개의 노드를 확인 및 연산
3. 값 업데이트
   1. 해당 리프노드와 연관된 모든 노드 갱신 : O(logN)

---

세그먼트 트리의 활용

세그먼트 트리는 다양한 문제에 활용됩니다:

1. 구간 합 문제: 배열의 특정 구간 합을 빠르게 계산.
2. 구간 최소/최대 문제: 구간 내 최소값/최대값 탐색.
3. 구간 업데이트 문제: 특정 구간의 값을 동시에 변경.
4. 2D 세그먼트 트리: 2차원 배열(예: 행렬)에서 구간 쿼리 처리.

---

세그먼트 트리 In JAVA

1. 트리 초기화

    import java.io.*;
    import java.util.*;

    public class Study {
        static int n;
        static long[] elements, tree;
        public static void main(String[] args) throws IOException {

            elements = new long[]{10, 1, 9, 4, 8, 5, 7, 12, 6, 3, 11, 2};

            n = elements.length;

            int treeSize = getTreeSize();
            tree = new long[treeSize];
            init(0,n-1,1);

            System.out.println(Arrays.toString(tree));
        }

        static int getTreeSize() {
            int h = (int)Math.ceil(Math.log(n)/Math.log(2)) +1;
            return (int)Math.pow(2, h)-1;
        }

        static long init(int start, int end, int node) {
            if(start == end) return tree[node] = elements[start];

            int mid = (start+end)/2;
            return tree[node] =  init(start, mid, node*2) +init(mid+1, end, node*2+1);
        }
    }

입력 배열 : elements

getTreeSize()는 트리의 높이를 계산하여 세그먼트 트리 배열의 크기를 구하는 메서드입니다.

완전 이진 트리가 아닌 경우에 필요한 리프노드의 개수만큼 메모리를 할당하기에 공간복잡도에서 효율성이 있습니다.

 

그러나 코드를 기억하기 힘들기 때문에 문제를 풀이할 때는 완전 이진 트리를 고려한 배열 크기 할당이 편리합니다.

long[] tree = new int[n<<1];

 

init()메서드의 경우 루트노드에서 재귀호출을 통해 세그먼트 트리 배열을 초기화하는 메서드입니다.

재귀가 아닌 리프노드에서부터 탐색하게 될 경우 아래와 같이 작성할 수 있습니다.

for(int i=0; i<elements.length; i++) {  //리프노드 입력
    tree[n+i] = elements[i];
}

for(int i=n-1; i>0; i--) {  //리프레벨-1에서 오른쪽부터 2개씩 합 계산
    tree[i] = tree[i*2] + tree[i*2+1];
}

---

2. 구간 합 구하기

 static long sum(int node, int start, int end, int left, int right){
    // 범위를 벗어나게 되는 경우 더할 필요 없음
    if(left > end || right < start){
        return 0;
    }

    // 범위 내 완전히 포함 시에는 더 내려가지 않고 바로 리턴
    if(left <= start && end <= right){
        return tree[node];
    }

    // 그 외의 경우 좌 / 우측으로 지속 탐색 수행
    return sum(node*2, start, (start+end)/2, left, right)+
        sum(node*2+1, (start+end)/2+1, end, left, right);
}

루트노드, 입력배열의 시작, 입력배열의 끝, 구간 시작, 구간 끝을 매개변수로 받습니다.

위에 설명한것과 마찬가지로 루트에서 이분탐색과 비슷하게 범위를 줄여가며 완전포함될 때 까지 탐색합니다.

만약 범위를 벗어난 곳으로 탐색 시에는 0을 반환합니다.

---

3. 값 업데이트

static void update(int node, int start, int end, int idx, long diff){
    // 만약 변경할 index 값이 범위 바깥이면 확인 불필요
    if(idx < start || end < idx) return;

    // 차를 저장
    tree[node] += diff;

    // 리프노드가 아니면 아래 자식들도 확인
    if(start != end){
		    int mid = (start+end)/2;
        update(node*2, start, mid, idx, diff);
        update(node*2+1, mid+1, end, idx, diff);
    }
}

루트노드, 입력배열의 시작, 입력배열의 끝, 업데이트한 인덱스, 기본값과의 차이를 매개변수로 받습니다.

기존 elements배열에서의 값 갱신도 해주어야 추후에 탐색에서 정확한 연산이 됩니다.

elements[0] = 변경값; //업데이트

루트노드에서부터 탐색을 시작하여 변경된 인덱스를 포함하는 구간에 한해서 차이를 갱신합니다.

 

---

레퍼런스

https://wikidocs.net/209446

06. 세그먼트 트리