[백준 10868] 최솟값, C++

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

10868번: 최솟값

본 문제는 구간의 최솟값을 구하는 문제다. 근데 입력이 100,000이다 그래서 O(n^2)으로 풀 수 없다. 입력이 큰데 구간의 최솟값을 구하는 문제는 세그먼트 트리를 이용해여 풀 수 있다. 세그먼트 트리를 이용하여 구간의 최솟값과, 구간의 합을 구할 수 있다.

#include <cstdio>
#include <vector>
#include <cmath>
 
using namespace std;
 
int Min(int x, int y) {
    if (x < y) return x;
    else return y;
}
 
void init(vector<int> &tree, vector<int> &a, int node, int start, int end) {
    if (start == end) tree[node] = a[start];
    else {
        init(tree, a, node*2, start, (start+end)/2);
        init(tree, a, node*2+1, (start+end)/2+1, end);
        tree[node] = Min(tree[node*2], tree[node*2+1]);
    }
}
 
int query(vector<int> &tree, int node, int start, int end, int i, int j) {
    if (i > end || j < start) return -1;
    if (i <= start && j >= end) return tree[node];
    int m1 = query(tree, node*2, start, (start+end)/2, i, j);
    int m2 = query(tree, node*2+1, (start+end)/2+1, end, i, j);
    if (m1 == -1) return m2;
    else if (m2 == -1) return m1;
    else return Min(m1, m2);
}
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> a(n);
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (h+1));
    vector<int> tree(tree_size);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    init(tree, a, 1, 0, n-1);
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", query(tree, 1, 0, n-1, x-1, y-1));
    }
}