Dynamic Range Minimum Queries

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

const int MOD = 1e9 + 7;

class SegmentTree {
    private:
        vector<int> tree;
        int n;

        void build(const vector<int>& values, int node, int start, int end) {
            if (start == end) {
                tree[node] = values[start];
            } else {
                int mid = (start + end) / 2;
                build(values, 2 * node + 1, start, mid);
                build(values, 2 * node + 2, mid + 1, end);
                tree[node] = min(tree[2 * node + 1], tree[2 * node + 2]);
            }
        }

        void update(int node, int start, int end, int idx, int value) {
            if (start == end) {
                tree[node] = value;
            } else {
                int mid = (start + end) / 2;
                if (start <= idx && idx <= mid) {
                    update(2 * node + 1, start, mid, idx, value);
                } else {
                    update(2 * node + 2, mid + 1, end, idx, value);
                }
                tree[node] = min(tree[2 * node + 1], tree[2 * node + 2]);
            }
        }

        int query(int node, int start, int end, int l, int r) {
            if (r < start || end < l) {
                return INT_MAX;
            }
            if (l <= start && end <= r) {
                return tree[node];
            }
            int mid = (start + end) / 2;
            int left_query = query(2 * node + 1, start, mid, l, r);
            int right_query = query(2 * node + 2, mid + 1, end, l, r);
            return min(left_query, right_query);
        }

    public:
        SegmentTree(const vector<int>& values) {
            n = values.size();
            tree.resize(4 * n);
            build(values, 0, 0, n - 1);
        }

        void update(int idx, int value) {
            update(0, 0, n - 1, idx, value);
        }

        int query(int l, int r) {
            return query(0, 0, n - 1, l, r);
        }
};

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

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

    SegmentTree st(values);

    for (int i = 0; i < q; ++i) {
        int type, aux1, aux2;
        cin >> type >> aux1 >> aux2;
        if (type == 1) {
            st.update(aux1 - 1, aux2);
        } else if (type == 2) {
            cout << st.query(aux1 - 1, aux2 - 1) << endl;
        }
    }

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED