세그먼트 트리(Segment Tree)

세그먼트 트리(Segment Tree)는 구간에 대한 정보를 빠르게 구해낼 수 있으며 완전 이진트리 형식의 구조를 가지는 자료구조입니다.

구간 최소값을 구하는 세그먼트 트리 예시

구간의 최솟값을 구하는 세그먼트 트리는 먼저 구하고자 하는 배열을 완전 이진트리의 최하단에 위치시킨 후, 모든 부모 노드가 자식 노드들 중 작은 값을 가지게 하며 트리를 완성시킵니다.

이를 통해 트리의 어떤 노드 X는 X의 하위 노드 중 최솟값을 가지게 됨은 자명합니다.

예를 들어 아래 배열을 사용한 세그먼트 트리의 구현에서 Tree[1]은 모든 원소의 최솟값이 오게 되고, Tree[2]는 하위 노드인 8~11번지의 최솟값이 들어있게 됩니다.
이들 중 원하는 범위 [L, R]에 필요한 노드를 골라서 구성할 것입니다.

위에서 완성된 세그먼트 트리에서 배열 D에 대한 범위 [L, R]의 최솟값을 찾아 보겠습니다.

주어진 L이 0이고 R이 5일 때, 세그먼트 트리로 옮겨보겠습니다.
트리로 옮겨진 점은 소문자 l, r로 표기하고, 이 값을 적당히 옮겨서 구하고자 하는 답인 D[L,R]의 최솟값을 구해 보겠습니다.

위의 l과 r사이의 범위를 모두 확인할 수 있는 노드는 다음과 같습니다.

빨간 동그라미가 그려진 두 노드 중 최솟값이 우리가 구하려는 범위의 최솟값이 됨을 알 수 있습니다. 두 노드중 왼쪽 노드는 D[0,3]의 최솟값, 오른쪽 노드는 D[4,5]의 최솟값을 가지기 때문입니다.

이 두 노드를 찾는 방법은 l, r을 구하고자 하는 범위를 벗어나지 않게 상위 노드로 옮기는 것입니다.

여기서 l의 의미는 현재 확인해야 할(확인되지 않은) 가장 왼쪽 위치를 포함하는 트리의 노드의 인덱스, r의 의미는 현재 확인해야 할 가장 오른쪽 위치를 포함하는 트리의 노드의 인덱스입니다.

배열로 구현된 1-based 이진트리 구조

배열로 구현된 1-based 세그먼트 트리에 대해 l과 r을 이용하여 답을 구하는 방법은 다음과 같습니다.
세그먼트 트리는 완전 이진트리이기 때문에 위와 같은 구조를 가짐을 참고합니다.

l 이 r보다 작거나 같을 때 다음을 반복합니다.

1) l 이 짝수일 때, l을 2로 나누어 준다.

2) l 이 홀수일 때, Tree[l] 값을 최솟값의 후보로 남겨두고 l을 2로 나누고 1을 더해준다.

3) r 이 홀수일 때 r을 2로 나누어 준다.

4) 4 이 짝수일 때, Tree[r] 값을 최솟값의 후보로 남겨두고 r을 2로 나누고 1을 빼준다.

l이 짝수라면 l의 부모노드의 왼쪽 자식을 의미합니다. l의 상위노드는 l의 범위를 포함하면서 l보다 더 큰 범위를 볼 수 있습니다.

l이 홀수라면 l의 부모노드의 오른쪽 자식을 의미합니다. l의 부모노드의 왼쪽노드는 우리가 확인하려는 범위를 벗어나기 때문에, 현재 트리의 l에 있는 값을 정답의 후보군으로 둔 후, l의 부모노드의 오른쪽 노드로 옮겨 확인되지 않은 오른쪽 범위를 확인해야 합니다.

r이 홀수인 경우는 r이 r의 부모노드의 오른쪽 자식이므로, r의 범위를 포함하여 더 왼쪽 범위를 확인하기 위해 부모노드로 옮겨줍니다.

r이 짝수인 경우는 r의 부모노드는 r의 범위를 벗어난 곳 까지 확인하기 때문에, r의 부모노드는 더이상 의미가 없습니다. 그러므로 기존 트리의 r에 있는 값을 정답의 후보군으로 둔 후, 부모노드의 왼쪽노드를 새로운 r로 두어 더 왼쪽범위까지 확인합니다.

당연히 l과 r의 의미에 따라 l이 r보다 크다면, 위의 루프를 돌 필요가 없습니다.
이를 위의 예제로 확인해보겠습니다.

이 자료구조의 시간 복잡도는 세그먼트 트리 구성에 O(N log N), 갱신에 O(log N), 구간 값을 알아내는데 O(log N)이 걸리므로 매우 빠르게 구간에 대한 정보를 얻을 수 있습니다.

최댓값, 최솟값뿐만 아니라 누적값을 비롯한 여러 정보들을 알맞은 변형을 통하여 빠르게 알아낼 수 있으며, 늦은 전파(lazy propagation)이라는 기법으로 구간 갱신을 효율적으로 개선할 수 있습니다.

그리고 위와 같은 구현은 Bottom-up 구현이라고 합니다.

동작은 유사하지만, 재귀를 활용한 Top-Down 구현 방법도 알아두시면 좋습니다. 시간 복잡도는 같지만, 상수가 다르므로 제한시간을 잘 고려하여 코드를 작성하시면 됩니다.

참고 : http://arkainoh.blogspot.com/2018/06/segment.tree.html

Java

입력	출력
7 1 -2 3 4 -5 -6 7 3 1 1 2 4 2 7	1 -2 -6

import java.util.ArrayList;
import java.util.Scanner;

class SegmentTree {
    ArrayList<Integer> tree;
    int s;

    public SegmentTree(int n) {
        for (s = 1; s < n; s *= 2);
        tree = new ArrayList<Integer>(s * 2);
        tree.add(0);
        for (int i = 1; i < s + s; i++)
            tree.add(Integer.MAX_VALUE);
    }

    void insert(ArrayList<Integer> d) {
        for (int i = s; i < s + d.size(); i++)
            tree.set(i, d.get(i - s));
        for (int i = s - 1; i >= 1; i--)
            tree.set(i, Integer.min(tree.get(i * 2), tree.get(i * 2 + 1)));
    }

    int getMin(int Left, int Right) {
        int l = Left + s - 1, r = Right + s - 1;
        int rval = Integer.MAX_VALUE;
        while (l <= r) {
            if (l % 2 == 0) l /= 2;
            else {
                rval = Integer.min(rval, tree.get(l));
                l = (l / 2) + 1;
            }
            if (r % 2 == 1) r /= 2;
            else {
                rval = Integer.min(rval, tree.get(r));
                r = (r / 2) - 1;
            }
        }
        return rval;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        SegmentTree T = new SegmentTree(n);

        ArrayList<Integer> v = new ArrayList<Integer>(n + 1);

        for (int i = 0; i < n; i++)
            v.add(sc.nextInt());

        T.insert(v);

        int m = sc.nextInt();

        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            System.out.println(T.getMin(x, y));
        }
    }
}