Segment Tree Implementation for Minimum number.

segment_rmq.cpp

#include<bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define sll set<ll>
#define mll map<ll,ll>
#define MOD 1000000007
#define fo(i,m,n) for(i=m;i<n;i++)
#define fore(i,m,n) for(i=m;i>=n;i--)

using namespace std;

ll Tree[3000000];
ll a[3000000];
void build(ll start,ll end,ll i)
{
	if(start==end)
	{
		Tree[i] = a[start];
		return ;
	}
	ll mid = (start+end)/2;
	build(start,mid,2*i);
	build(mid+1,end,2*i+1);
	Tree[i] = min(Tree[2*i] ,Tree[2*i+1]);
}

void up(ll start,ll end,ll i,ll index,ll val)
{
    if(start==end)
    {
        a[index]=val;
        Tree[i] = val;
        return ; 
    }
    
    ll mid=(start+end)/2;
    if(start<=index and index <= mid)
    {
        up(start, mid, 2*i,index,val);
    }
    else
    {
        up(mid+1, end, 2*i+1,index,val); 
    }
    Tree[i] = min(Tree[2*i],Tree[2*i+1]);
}

ll que(ll start,ll end,ll i,ll l,ll r)
{
    if(r<start or l>end)
        return INT_MAX;
    if(l<=start and r>=end)
    {
        return Tree[i];
    }
    ll mid = (start+end)/2;
    return min(que(start,mid,2*i,l,r) , que(mid+1,end,2*i+1,l,r));
}

int main()
{
    ll n,q;
    memset(Tree,INT_MAX,sizeof(Tree));
    cin >> n >> q;
    for(ll i=1;i<=n;i++)
        cin >> a[i];
    build(1,n,1);
    while(q--)
    {
        char m;
    	ll x,y;
    	cin >> m >> x >> y;
		if(m == 'u')
		    up(1,n,1,x,y);
		else
			cout << que(1,n,1,x,y)<<endl;;
	}
    return 0;
}