세그먼트 트리(Segment Tree)

개념

---

세그먼트 트리는 간격에 대한 정보를 저장하는 자료구조입니다.

이를 이용하면 구간 합, 구간 최댓값/최솟값 들을 빠르게 구할 수 있습니다.

 

보통 구간 합을 구하는 방법은 해당 구간을 전부 탐색하면서 합을 구하는 방식입니다.

이 방법은 O(N)의 시간이 걸립니다.

하지만 세그먼트 트리의 경우 구간을 탐색하는데 O(lgN)의 시간밖에 걸리지 않습니다.

 

해당 글은 구간의 최솟값들을 구하는 방법으로 설명하겠습니다.

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

14438번: 수열과 쿼리 17

 

 

트리의 구조

---

트리의 노드들은 특정 구간을 의미합니다.

 

예를 들어 0~9 인덱스를 저장한다고 가정하겠습니다.

해당 구간을 절반만큼 쪼개어서( (0 + 9) / 2 ) 두 개의 자식 노드에 저장합니다.

그러면 자식 노드에는 0~4, 5~9의 구간이 저장됩니다.

 

이런 방식으로 자식 노드에 현재 노드의 구간의 절반을 쪼개어서 각각 저장하고

노드의 구간이 1~1처럼 한개의 숫자만을 나타내면 자식을 더 이상 만들지 않습니다.

 

0~9 인덱스를 저장한다고 가정하고 트리를 만들어 보았습니다.

그렇다면 아래의 구조를 나타내게 됩니다.

 

각각의 노드는 구간을 나타낸다고 하면 노드의 내용에는 해당 구간의 최솟값들이 담기게 됩니다.

 

 

트리의 탐색

---

트리의 탐색은 트리를 내려가면서 탐색을 원하는 구간에 해당하는 노드가 발견된다면 그 값을 가지고 빠져나오게 됩니다.

 

예를 들어, 3~5 구간을 탐색한다고 가정해 보겠습니다.

먼저 루트노드에서 자식을 검사합니다. 0~4, 5~9는 3~5를 포함하는 값이 있으므로 두 개의 노드 모두 탐색합니다.

0~4 노드에서는 0~2노드는 3~5 중 포함하는 값이 없으므로 탐색하지 않고 3~4는 해당 구간 전체가 3~5에 포함되므로 리턴됩니다.

5~9 노드에서는 5를 찾기 위해서 계속 내려가서 5 노드를 만날 때 리턴하게 됩니다.

 

리턴되는 값들을 부모 노드에서 모아 그중 최솟값들만 리턴한다면 루트 노드에는 해당 구간의 최솟값들만 모이게 됩니다.

 

 

코드

---

// 트리 구성
private static int makeTree(int s, int e, int node) {
    if(s == e) return tree[node] = arr[s];
    int m = (s + e) / 2;
    return tree[node] = Math.min(makeTree(s, m, node * 2), makeTree(m + 1, e, node * 2 + 1));
}

// 노드의 값 변경
private static int change(int s, int e, int node, int i, int v) {
    if(s == i && e == i) return tree[node] = v;
    if(e < i || i < s) return tree[node];
    int m = (s + e) / 2;
    return tree[node] = Math.min(change(s, m, node * 2, i, v), change(m + 1, e, node * 2 + 1, i, v));
}

// 구간의 최솟값 찾기
private static int findMin(int s, int e, int node, int left, int right) {
    if(left <= s && e <= right) return tree[node];
    if(e < left || right < s) return Integer.MAX_VALUE;
    int m = (s + e) / 2;
    return Math.min(findMin(s, m, node * 2, left, right), findMin(m + 1, e, node * 2 + 1, left, right));
}

 

 

References

---

https://minusi.tistory.com/entry/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%ACSegment-Tree-Index-Tree

https://www.crocus.co.kr/648