CSES – Dynamic Range Minimum Queries

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
struct seg{
    int L,R;
    int data;
    int lson, rson;
} ST[2*maxn];
vector<int> v;
int stptr = 1;
void build(int L,int R,int idx){
    ST[idx].L = L, ST[idx].R = R;
    if(L + 1 == R){
        ST[idx].data = v[L];
        return;
    }
    int mid = (L+R) / 2;
    int lson = ST[idx].lson = stptr++;
    int rson = ST[idx].rson = stptr++;
    build(L,mid,lson);
    build(mid,R,rson);
    ST[idx].data = min(ST[lson].data, ST[rson].data);
}
void modify(int pos,int x,int idx){
    if(ST[idx].L + 1 == ST[idx].R){
        ST[idx].data = x;
        return;
    }
    int mid = (ST[idx].L+ST[idx].R) / 2;
    int lson = ST[idx].lson, rson = ST[idx].rson;
    if(pos < mid) modify(pos,x,lson);
    else modify(pos,x,rson);
    ST[idx].data = min(ST[lson].data, ST[rson].data);
}
int query(int L,int R,int idx){
    if(ST[idx].L == L && ST[idx].R == R){
        return ST[idx].data;
    }
    int mid = (ST[idx].L+ST[idx].R) / 2;
    int lson = ST[idx].lson, rson = ST[idx].rson;
    if(R <= mid) return query(L,R,lson);
    if(L >= mid) return query(L,R,rson);
    return min(query(L,mid,lson), query(mid,R,rson));
}
signed main(){
    int n,q; cin>>n>>q;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        v.push_back(x);
    }
    build(0,n,0);
    while(q--){
        int op,a,b; cin>>op>>a>>b;
        if(op == 1){
            modify(a-1,b,0);
        }
        else cout<<query(a-1,b,0)<<"\n";
    }
    return 0;
}