Dynamic Range Minimum Queries

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

void updateTree(int k, int u, int t, vector<int>& tree){
    k += t;
    tree[k] = u;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = min(tree[2*k], tree[2*k+1]);
    }
}

int findMin(int a, int b, int t, vector<int>& tree){
    a += t; 
    b += t;
    int m = INT_MAX;
    while (a <= b) {
        if (a%2 == 1) m = min(tree[a++], m);
        if (b%2 == 0) m = min(tree[b--], m);
        a /= 2; b /= 2;
    }
    return m;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> num(n);
    for (int i = 0; i < n; i++){
        cin >> num[i];
    }
    vector<vector<int>> queries(q, vector<int>(3));
    for (int i = 0; i < q; i++){
        for (int j = 0; j < 3; j++){
            cin >> queries[i][j];
        }
    }
    
    int t = 1;
    while (t < n) t *= 2;
    vector<int> segmentTree(2*t, INT_MAX);
    for (int i = 0; i < n; i++) {
        segmentTree[t+i] = num[i];
    }
    for (int i = t-1; i >= 1; i--){
        segmentTree[i] = 
            min(segmentTree[2*i], segmentTree[2*i+1]);
    }
    
    for (int i = 0; i < q; i++){
        if (queries[i][0] == 1){
            int k = queries[i][1];
            int u = queries[i][2];
            updateTree(k-1, u, t, segmentTree);
        } else {
            int a = queries[i][1];
            int b = queries[i][2];
            int sol = findMin(a-1, b-1, t, segmentTree);
            cout << sol << endl;
        }
    }
    
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED