Dynamic Range Minimum Queries

// g++ -std=c++17 -O2 -pipe -Wall -Wextra a.cpp -o a
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1'000'000'007;
const int INF = 1e9;
#define ll long long
#define fast                     \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);

struct SegmentTree
{
    int n;
    vector<ll> seg;

    SegmentTree(const vector<ll> &a)
    {
        n = (int)a.size();
        seg.assign(4 * n, INF);
        build(0, 0, n - 1, a);
    }

    void build(int node, int l, int r, const vector<ll> &a)
    {
        if (l == r)
        {
            seg[node] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        int left = 2 * node + 1;  // left child
        int right = 2 * node + 2; // right child
        build(left, l, mid, a);
        build(right, mid + 1, r, a);
        seg[node] = min(seg[left], seg[right]);
    }

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

    void update(int node, int l, int r, int idx, ll val)
    {
        if (l == r)
        {
            seg[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        int left = 2 * node + 1;
        int right = 2 * node + 2;
        update(left, l, mid, idx, val);
        update(right, mid + 1, r, idx, val);
        seg[node] = min(seg[left], seg[right]);
    }

    // minimum range on [ql, qr]
    ll query(int ql, int qr)
    {
        return query(0, 0, n - 1, ql, qr);
    }

    ll query(int node, int l, int r, int ql, int qr)
    {
        if (qr < l || r < ql)
            return INF;
        if (ql <= l && r <= qr)
            return seg[node];
        // partial part
        int mid = (l + r) / 2;
        int left = 2 * node + 1;
        int right = 2 * node + 2;
        return min(query(left, l, mid, ql, qr),
                   query(right, mid + 1, r, ql, qr));
    }
};

int main()
{
    fast;

    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    SegmentTree st(a); // SEGMENT TREE
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int id, val;
            cin >> id >> val;
            id--;
            st.update(id, val);
        }
        else
        {
            int ql, qr;
            cin >> ql >> qr;
            ql--;
            qr--;
            cout << st.query(ql, qr) << '\n';
        }
    }

    return 0;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: TIME LIMIT EXCEEDED