최솟값 - 10868

//10868 - 최솟값
 
#include <iostream>
#include <vector>
using namespace std;
 
#define INF 1000000001
 
int N, M;
int arr[100001];
 
struct SegmentTree
{
    int n;
    vector<int> tree;
 
    SegmentTree(int n) : n(n), tree(n*4+1)
    {
        init(1, n, 1);
    }
 
    int init(int left, int right, int node)
    {
        if(left == right) return tree[node] = arr[left];
        int mid = (left + right)/2;
        return tree[node] = min(init(left, mid, node*2), init(mid+1, right, node*2+1));
    }
 
    int query(int left, int right, int nodeLeft, int nodeRight, int node)
    {
        if(right < nodeLeft || nodeRight < left) return INF;
        if(left <= nodeLeft && nodeRight <= right) return tree[node];
 
        int mid = (nodeLeft + nodeRight)/2;
        return min(query(left, right, nodeLeft, mid, node*2), 
                   query(left, right, mid+1, nodeRight, node*2+1));
    }
 
    int query(int left, int right)
    {
        return query(left, right, 1, n, 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i<=N; ++i)
        cin >> arr[i];
    SegmentTree st(N);
    int x, y;
    for(int i = 0; i<M; ++i)
    {
        cin >> x >> y;
        cout << st.query(x, y) << "\n";
    }
}

 

 

 

 

 

 

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

10868번: 최솟값

 

 

 

 

 

 

최솟값

세그먼트 트리를 이용해 구간의 최소값을 구했습니다.