Dynamic Range Minimum Queries

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

void update(int k, long long x, vector<long long>& tree, int n) {
    k += n;
    tree[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = min(tree[2*k], tree[2*k+1]);
    }
}

long long minimum(int a, int b, vector<long long>& tree, int n) {
    a += n; b += n;
    long long s = LLONG_MAX;
    while (a <= b) {
        if (a % 2 == 1) s = min(s, tree[a++]);
        if (b % 2 == 0) s = min(s, tree[b--]);
        a /= 2; b /= 2;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    vector<long long> tree(2*n);

    for (int i = 0; i < n; i++) {
        tree[n+i] = nums[i];
    }

    for (int i = n-1; i > 0; i--) {
        tree[i] = min(tree[2*i], tree[2*i+1]);
    }

    for (int i = 0; i < q; i++) {
    int t;
    long long a, b;
    cin >> t >> a >> b;

    if (t == 1) {

        int k = a - 1;   
        long long u = b; 
        update(k, u, tree, n);
    } else {
        
        int l = a - 1;  
        int r = b - 1;
        cout << minimum(l, r, tree, n) << "\n";
    }
}


    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED