Dynamic Range Minimum Queries

#include <bits/stdc++.h>

using namespace std;

#define F(n) for (int i = 0; i < n; ++i)


void    update(int k, int n, int x, std::vector<int>& tree) {
    k += n;
    tree[k] = x;


    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = min(tree[2*k], tree[2*k+1]);
    }

}

int     find_min(int a, int b, int n, std::vector<int>& tree) {
    a += n; b += n;
    int min_num = INT_MAX;

    while (a <= b) {
        if (a%2 == 1) min_num = std::min(min_num, tree[a++]);
        if (b%2 == 0) min_num = std::min(min_num, tree[b--]);
        a /= 2; b /= 2;
    }

    return (min_num);
}

int main() {
    int n, q;

    cin >> n >> q;

    std::vector<int> tree(2*n, 0);

    for (int i = 0; i < n; ++i) {
        int tmp;

        cin >> tmp;
        update(i, n, tmp, tree);
    }

    // for (size_t i = 0; i < tree.size(); ++i) {
    //     cout << "tree[" << i << "]: " << tree[i] << endl; 
    // }

    vector<int> result;
    F(q) {
        int type, a, b;
        cin >> type >> a >> b;

        if (type == 1) {
            update(a - 1, n, b, tree);
        } else if (type == 2) {
            int min = find_min(a - 1, b - 1, n, tree);
            // cout << "min: " << min << endl;
            result.push_back(min);
        }
    }

    F(static_cast<int>(result.size())) {
        cout << result[i] << endl;
    }

    return (0);
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED