Segment tree

segtree.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class SegmentTree {
    struct Node {
        pair<ll, ll> range;
        ll left = 0, right = 0, value = INT_MAX;
    };

    vector<Node> node;

    void build(ll id, ll l, ll r) {
        node[id].range = {l, r};

        if (l == r) {
            return;
        }

        node[id].left = id * 2;
        node[id].right = id * 2 + 1;

        build(node[id].left, l, (l + r) / 2);
        build(node[id].right, (l + r) / 2 + 1, r);
    }

    void _update(ll id, ll i, ll val) {
        if (id == 0) {
            return;
        }

        auto [l, r] = node[id].range;

        if (i < l || r < i) {
            return;
        }

        if (l == r) {
            node[id].value = val;
            return;
        }

        _update(node[id].left, i, val);
        _update(node[id].right, i, val);

        node[id].value = min(node[node[id].left].value, node[node[id].right].value);
    }

    ll _query(ll id, ll a, ll b) {
        if (id == 0) {
            return INT_MAX;
        }

        auto [l, r] = node[id].range;

        if (b < l || r < a) {
            return INT_MAX;
        }

        if (a <= l && r <= b) {
            return node[id].value;
        }

        return min(_query(node[id].left, a, b), _query(node[id].right, a, b));
    }

   public:
    SegmentTree(ll n) {
        node.resize(4 * n);
        build(1, 0, n - 1);
    }

    void update(ll i, ll x) {
        _update(1, i, x);
    }

    ll query(ll l, ll r) {
        return _query(1, l, r);
    }
};

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    ll n, q;
    cin >> n >> q;

    SegmentTree tree(n);

    for (ll i = 0; i < n; i++) {
        ll x;
        cin >> x;

        tree.update(i, x);
    }

    while (q--) {
        ll t;
        cin >> t;

        if (t == 1) {
            ll k, u;
            cin >> k >> u;

            tree.update(k - 1, u);
        } else {
            ll a, b;
            cin >> a >> b;

            cout << tree.query(a - 1, b - 1) << '\n';
        }
    }
}