Dynamic Range Minimum Queries

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

using namespace std;

const int INF = 2e9 + 7;

struct SegmentTree {
    int size;
    vector<int> tree;

    SegmentTree(int n, const vector<int>& a) {
        size = 1;
        while (size < n) size <<= 1;
        tree.assign(2 * size, INF);

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

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

    void update(int k, int u) {
        k += size;
        tree[k] = u;
        for (k >>= 1; k > 0; k >>= 1) {
            tree[k] = min(tree[2 * k], tree[2 * k + 1]);
        }
    }

    int query(int l, int r) {
        int res = INF;
        for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = min(res, tree[l++]);
            if (r & 1) res = min(res, tree[--r]);
        }
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    SegmentTree st(n, a);

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int k, u;
            cin >> k >> u;
            --k; 
            st.update(k, u);
        } else {
            int a_idx, b_idx;
            cin >> a_idx >> b_idx;
            --a_idx; --b_idx; 
            cout << st.query(a_idx, b_idx) << "\n";
        }
    }

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED