range_min_segment_tree.cpp

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = (int)3e5 + 10;
const int INF = (int)1e18;
int a[N];

class MinST{
    int t[4 * N];
    public:
    void build(int node, int l, int r){ // O(n)
        if(l == r){
            t[node] = a[r];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);
        t[node] = min(t[2 * node], t[2 * node + 1]);
    }
    void update(int node, int l, int r, int i, int val){ // O(log n)
        if(l > i || r < i)  return;
        if(l == r){
            t[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        update(2 * node, l, mid, i, val);
        update(2 * node + 1, mid + 1, r, i, val);
        t[node] = min(t[2 * node], t[2 * node + 1]);
    }
    int rmin(int node, int l1, int r1, int l, int r){ // O(log n)
        if(l1 > r || r1 < l)    return INF;
        if(l1 >= l && r1 <= r)  return t[node];
        int mid = (l1 + r1) / 2;
        return min(rmin(2 * node, l1, mid, l, r), rmin(2 * node + 1, mid + 1, r1, l, r));  
    }
};


int32_t main(){
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int q; cin >> q;
    MinST seggs;
    seggs.build(1, 1, n);
    while(q--){
        int type; cin >> type;
        if(type == 1){
            int i, val; cin >> i >> val;
            seggs.update(1, 1, n, i, val);
        }else{
            int l, r; cin >> l >> r;
            cout << seggs.rmin(1, 1, n, l, r) << '\n';
        }
    }
    return 0;
}