Dynamic Range Minimum Queries

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

class SegmentTree {
public:
    SegmentTree(const vector<int>& data) {
        n = data.size();
        tree.resize(2 * n);
        build(data);
    }

    void update(int index, int value) {
        int pos = index + n;
        tree[pos] = value;
        while (pos > 1) {
            pos /= 2;
            tree[pos] = min(tree[2 * pos], tree[2 * pos + 1]);
        }
    }

    int query(int left, int right) {
        int result = numeric_limits<int>::max();
        left += n;
        right += n + 1;
        while (left < right) {
            if (left % 2 == 1) {
                result = min(result, tree[left]);
                left++;
            }
            if (right % 2 == 1) {
                right--;
                result = min(result, tree[right]);
            }
            left /= 2;
            right /= 2;
        }
        return result;
    }

private:
    vector<int> tree;
    int n;

    void build(const vector<int>& data) {
        for (int i = 0; i < n; ++i) {
            tree[n + i] = data[i];
        }
        for (int i = n - 1; i > 0; --i) {
            tree[i] = min(tree[2 * i], tree[2 * i + 1]);
        }
    }
};

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

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

    SegmentTree seg_tree(arr);
    for (int i = 0; i < q; ++i) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) {
            seg_tree.update(x - 1, y); // Update at position x-1
        } else {
            cout << seg_tree.query(x - 1, y - 1) << '\n'; // Query from x-1 to y-1
        }
    }

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED