Minimum In Subarray Segment Tree

#include<bits/stdc++.h>
using namespace std;
void BulidTree(int * arr,int start,int end,int i,int * tree)
{
    if(start==end)
    {
     	tree[i]=arr[start];
        return;
    }
        
    int mid=start+(end-start)/2;
    BulidTree(arr,start,mid,2*i,tree);
    BulidTree(arr,mid+1,end,(2*i)+1,tree);
    tree[i]=min(tree[2*i],tree[(2*i)+1]);
    
}
int query(int * tree,int start,int end,int i,int left,int right)
{
    //completely outside given range
    if(start>right||end<left)
        return INT_MAX;
    //completely inside given range
    if(start>=left&& end<=right)
    return tree[i];
    
    //partially inside and outside
    int mid=start+(end-start)/2;
    
    int ans1=query(tree,start,mid,2*i,left,right);
    
    int ans2=query(tree,mid+1,end,(2*i)+1,left,right);
    return min(ans1,ans2);
}
void updateTree(int * tree,int s,int e,int i,int ind,int val)
{
    if(s==e)
    {
        
        tree[i]=val;
        return;
    }
    
    int mid=s+(e-s)/2;
    
    if(ind>mid)
    {
        updateTree(tree,mid+1,e,(2*i)+1,ind,val);
    }
    else
        updateTree(tree,s,mid,(2*i),ind,val);
    tree[i]=min(tree[2*i],tree[(2*i)+1]);
}
int main(){
    
    // write your code here
    int n,t;
    cin>>n>>t;
    int * arr=new int[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    int * tree=new int[4*n];
    BulidTree(arr,0,n-1,1,tree);
    while(t--)
    {
        char c;
        
        cin>>c;
        if(c=='q')
        {
            int l,r; 
            cin>>l>>r;
            cout<<query(tree,0,n-1,1,l-1,r-1)<<endl;
            continue;
        }
        else{
            int x, y;
			cin>>x>>y;
            updateTree(tree,0,n-1,1,x-1,y);
            
        }
    }
    
    return 0;
}



Post a Comment

Please do not enter any spam link in the comment box.