세그먼트 트리 코드

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

const int INF = 1111111111;

void init(vector<int>& input, vector<int>& tree, int node, int start, int end){
    if (start == end) {
        tree[node] = input[start];
        return;
    }
    init(input, tree, 2*node, start, (start+end)/2);
    init(input, tree, 2*node+1, (start+end)/2+1, end);
    tree[node] = min(tree[2*node], tree[2*node+1]);
    return;
}

int findMin(vector<int>& tree, int node, int start, int end, int left, int right){
    if (left > end || right < start) {
        return INF;
    } else if (left <= start && end <= right){
        return tree[node];
    }
    int a = findMin(tree, 2*node, start, (start+end)/2, left, right);
    int b = findMin(tree, 2*node+1, (start+end)/2+1, end, left, right);
    return min(a, b);
}


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

    int n, m;
    cin >> n >> m;
    int h = int(ceil(log2(n)))+1;
    int treeSize = (1 << h);
    vector<int> tree(treeSize, INF);
    vector<int> a(n);

    for (int i = 0; i < n; i++) {
       cin >> a[i];
    }
    init(a, tree, 1, 0, n-1);

    for (int i = 0; i < m; i++) {
        int left, right;
        cin >> left >> right;
        cout << findMin(tree, 1, 0, n-1, left-1, right-1) << '\n';
    }

}

좋은 웹페이지 즐겨찾기