Skip to content

Instantly share code, notes, and snippets.

@onkar27
Created January 21, 2018 13:09
Show Gist options
  • Save onkar27/4ce7f1c1f4e1f59cc4c0e1ed4425d702 to your computer and use it in GitHub Desktop.
Save onkar27/4ce7f1c1f4e1f59cc4c0e1ed4425d702 to your computer and use it in GitHub Desktop.
Segment Tree Implementation for Minimum number.
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment