세그먼트 트리란?

주어진 구간에 대한 정보(누적합, 최대값, 최소값 등)을 효율적으로 저장하고 탐색하기 위한 자료구조입니다.

배열을 이용하여 트리를 구현하며, 각 노드에는 특정 구간(left ~ right)에 대한 정보(누적합, 최대값, 최소값 등)를 저장하여, 특정 범위에 대한 정보가 필요할 때 빠르게 접근할 수 있도록 합니다.

이러한 세그먼트 트리의 시간복잡도는 logn, 최악의 경우 nlogn으로써.
일반적인 선형 탐색의 시간복잡도가 n인것에 비해서 빠르게 자료를 처리할 수 있다는 장점이 있습니다.

다만, 세그먼트 트리의 단점에는 메모리 자원을 많이 필요로 한다는 것이 있습니다.

선형탐색을 위한 배열의 크기 = n
세그먼트 트리를 위한 배열의 크기 = 4*n

조금 더 정확히는,
주어진 배열의 크기가 N이라고 할 때.
N보다 크면서 가장 가까운 2의 제곱수. 예를 들어 N이 10이라면, 10보다 크면서 가장 가까운 제곱수인 16을 구하고.
16에 2를 곱한 값(32)을 배열의 크기로 설정하는 것입니다.
1 << static_cast<int>(ceil(log2(N)))

여기서 위의 공식을 거치지 않고 4*n을 하는 것은, 4n의 값이 세그먼트 트리의 값보다 무조건 큰 값이 나오기 때문입니다. (다소 메모리의 낭비는 있습니다.)

상단의 그림은 0~9까지의 데이터를 저장한 배열을 세그먼트 트리화 하여, 저장한 트리의 그래프입니다.

구현

초기화(initialization)

주어진 배열에 대해서 세그먼트 트리를 생성하고, 필요한 정보를 저장하는 과정입니다.
구간을 분할하여, 각 노드에 해당 구간의 정보(누적합, 최소최대값 등)를 저장하는데, 일반적으로 재귀적인 방식을 이용한 Top-Down방식을 이용하여 구현합니다.

쿼리(query)

원하는 구간에 대한 정보를 검색하는 기능입니다.
필요한 구간을 트리의 노드와 비교하면서 필요한 정보를 재귀적인 방식으로 찾아갑니다.

left와 right는 검색할 범위를 나타냅니다.
start와 end는 현재 인덱싱된 트리의 노드 범위를 나타내며, 검색할 구간인 left-right 구간과 비교하여, 안쪽에 있다면 값을 리턴해줍니다.

만약 범위를 벗어났다면, 리미트값을 초과한 값을 리턴해, 선택되지 않도록 해줍니다.

코드

문제 링크

N의 범위를 갖는 배열 내에서
M개의 질의에 대한 답을 출력하는 문제입니다.

질의는 N범위 내에 해당하는 정수 a에서 b까지의 범위 내에서 최소값과 최대값을 구하는 것입니다.

N과 M의 크기가 크기 때문에, 일반적인 선형 탐색. 혹은 정렬을 이용한 풀이로는 답을 구할 수 없습니다.

여기서 필요한 것이 세그먼트 트리입니다.
N범위에 해당하는 트리를 구현하고, 각 트리에 범위에 해당하는 최소값과 최대값을 각각 저장(이중배열)하여 질의에 따라 접근하여 답을 구하였습니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;

vector<long long> nums;
vector<vector<long long>> tree;

void init(int now, int left, int right) 
{
    if (left == right) 
    {
        tree[now][0] = nums[left]; // 최소값
        tree[now][1] = nums[left]; // 최대값
        return;
    }
    int mid = (left + right) / 2;
    init(now * 2, left, mid);
    init(now * 2 + 1, mid + 1, right);
    tree[now][0] = min(tree[now * 2][0], tree[now * 2 + 1][0]); // 왼쪽 자식의 최소값과 오른쪽 자식의 최소값 중 작은 값
    tree[now][1] = max(tree[now * 2][1], tree[now * 2 + 1][1]); // 왼쪽 자식의 최대값과 오른쪽 자식의 최대값 중 큰 값
}

pair<long long, long long> query(int now, int start, int end, int left, int right) 
{
    if (start > right || end < left) 
    {
        return { LLONG_MAX, LLONG_MIN };
    }
    if (left <= start && end <= right) 
    {
        return { tree[now][0], tree[now][1] };
    }
    int mid = (start + end) / 2;

    auto left_result = query(now * 2, start, mid, left, right);
    auto right_result = query(now * 2 + 1, mid + 1, end, left, right);

    long long min_val = min(left_result.first, right_result.first);
    long long max_val = max(left_result.second, right_result.second);
    
    return { min_val, max_val };
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;

    nums.resize(N);
    tree.resize(4 * N, vector<long long>(2));

    for (int i = 0; i < N; ++i) 
    {
        cin >> nums[i];
    }

    init(1, 0, N - 1);

    for (int i = 0; i < M; ++i) 
    {
        int a, b;
        cin >> a >> b;
        auto result = query(1, 0, N - 1, a - 1, b - 1);
        cout << result.first << " " << result.second << '\n';
    }

    return 0;
}