Dynamic Range Minimum Queries

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void add(int k, int x, vector<int>& tree, int n) {
    k = k - 1 + n;
    tree[k] = x;
    for (int i = k/2; i >= 1; i /= 2) {
        if(tree[i*2] < tree[i*2+1]) tree[i] = tree[i*2];
        else tree[i] = tree[i*2+1];
    }
}

int minimum(int a, int b, const vector<int>& tree, int n) {
    int l = a - 1 + n;
    int r = b + n; 
    int res = 2e9;

    while (l < r) {
        if (l % 2 != 0) res = min(res, tree[l++]);
        if (r % 2 != 0) res = min(res, tree[--r]);
        l /= 2;
        r /= 2;
    }
    return res;
}

int main() {
    int n, q;
    cin >> n >> q;

    vector<int> segment_tree(n*2, 0);
    for (int i = n; i < n*2; i++) {
        cin >> segment_tree[i];
    }

    for(int i = n - 1; i > 0; i--){
        if(segment_tree[i* 2] < segment_tree[i * 2 + 1]) segment_tree[i] = segment_tree[i* 2];
        else segment_tree[i] = segment_tree[i* 2 + 1];
    }

    int a,b,c;
    for(int i = 0; i < q; i++){
        cin >> a >> b >> c;
        if(a == 1){
            add(b, c, segment_tree, n);
        }
        else{
            cout << minimum(b,c,segment_tree,n) << endl;
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED