Dynamic Range Minimum Queries

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

typedef long long ll;
const ll INF = 1e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, q;
    cin >> n >> q;
    
    vector<ll> arr(n);
    for(auto &x: arr){
        cin >> x;
    }
    
    // Build the segment tree
    int size = 1;
    while(size < n) size <<=1;
    
    vector<ll> segtree(2*size, INF);
    
    // Set the leaves
    for(int i=0; i<n; ++i){
        segtree[size + i] = arr[i];
    }
    
    for(int i=size-1; i>=1; --i){
        segtree[i] = min(segtree[2*i], segtree[2*i +1]);
    }
    
    while(q--){
        int type;
        cin >> type;
        if(type ==1){
            int k;
            ll u;
            cin >> k >> u;
            k--;
            segtree[size + k] = u;
            int pos = size + k;
            while(pos >1){
                pos /=2;
                segtree[pos] = min(segtree[2*pos], segtree[2*pos +1]);
            }
        }
        else if(type ==2){
            int a, b;
            cin >> a >> b;
            a--; b--;
            ll res = INF;
            int l = size + a;
            int r = size + b;
            r++;
            while(l < r){
                if(l%2 ==1){
                    res = min(res, segtree[l]);
                    l++;
                }
                if(r%2 ==1){
                    r--;
                    res = min(res, segtree[r]);
                }
                l /=2;
                r /=2;
            }
            cout << res << "\n";
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED