segment_tree.cpp

// author: 08vivek08

#include <bits/stdc++.h>
using namespace std;

#define int long long

int mod = 1e9 + 7;

struct segment_tree
{
private:
    vector<int> values;
    int size;

    //////////////////////////////////////////////////////////////////////////////
    // neutral value to be changed according to the operation
    int neutral = INT_MAX;
    int merge(int a, int b)
    {
        // min to be changed into corresponding associative operation
        return min(a, b);
    }
    int single(int v)
    {
        // return value to be changed according to the operation
        return v;
    }
    //////////////////////////////////////////////////////////////////////////////

    /*****************************************************************************
    *   0 based indexing of segment tree and 0 based indexing of input array     *
    *   segment_tree st = segment_tree(n);                                       *
    *   point update : (i,val), where 0<=i<=n-1 & n is size of array             *
    *   range query : [l,r]                                                      *
    *   set : arr[i] = val                                                       *
    *   query : min[l, r]                                                        *
    *****************************************************************************/
public:
    segment_tree(int n)
    {
        size = 1;
        while (size < n)
            size *= 2;
        values.assign(2 * size, neutral);
    }
    void set(int i, int val, int x, int lx, int rx)
    {
        if (rx - lx == 0)
        {
            values[x] = single(val);
            return;
        }
        int m = (lx + rx) / 2;
        if (i <= m)
        {
            set(i, val, 2 * x + 1, lx, m);
        }
        else
        {
            set(i, val, 2 * x + 2, m + 1, rx);
        }
        values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
    }
    void set(int i, int val)
    {
        set(i, val, 0, 0, size - 1);
    }
    int query(int l, int r, int x, int lx, int rx)
    {
        if (lx > r || l > rx)
        {
            return neutral;
        }
        if (lx >= l && rx <= r)
            return values[x];
        int m = (lx + rx) / 2;
        int s1 = query(l, r, 2 * x + 1, lx, m);
        int s2 = query(l, r, 2 * x + 2, m + 1, rx);
        return merge(s1, s2);
    }
    int query(int l, int r)
    {
        return query(l, r, 0, 0, size - 1);
    }
};

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;
    for (int T = 1; T <= t; T++)
    {
        int n, m;
        cin >> n >> m;
        // code
        segment_tree st = segment_tree(n);
        for (int i = 0; i < n; i++)
        {
            int a;
            cin >> a;
            st.set(i, a);
        }
        while (m--)
        {
            int a, b, c;
            cin >> a >> b >> c;
            if (a == 1)
            {
                st.set(b, c);
            }
            else
            {
                cout << st.query(b, c - 1) << "\n";
            }
        }
    }
    return 0;
}