Scribd
Upload
52 views2 pages

Range - Query - Segment Tree - Range Min and Range Update

The document contains a C++ implementation of a segment tree for range minimum queries and point updates. It includes functions to build the segment tree, query the minimum value in a given range, and update values in the array. The main function reads input for the size of the array, the array elements, and processes multiple queries based on user input.

Uploaded by

Nikhil baghel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
52 views2 pages

Range - Query - Segment Tree - Range Min and Range Update

The document contains a C++ implementation of a segment tree for range minimum queries and point updates. It includes functions to build the segment tree, query the minimum value in a given range, and update values in the array. The main function reads input for the size of the array, the array elements, and processes multiple queries based on user input.

Uploaded by

Nikhil baghel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

#include<bits/stdc++.

h>
using namespace std;
void build(int idx,int low,int high,int arr[],int seg[])
{
if(low==high)
{
seg[idx]=arr[low];
return;
}
int mid=(low+high)/2;
build(2*idx+1,low,mid,arr,seg);
build(2*idx+2,mid+1,high,arr,seg);
seg[idx]=min(seg[2*idx+1],seg[2*idx+2]);
}
int query(int idx,int low,int high,int l,int r,int seg[])
{
// no overlap
//low high l r l r low high
if(high<l||r<low)
return INT_MAX;
//complete overlap l low high r
//partial overlap case
else if(l<=low&&high<=r)
{
return seg[idx];
}
int mid=(low+high)/2;
int left=query(2*idx+1,low,mid,l,r,seg);
int right=query(2*idx+2,mid+1,high,l,r,seg);
return min(left,right);
}
void update(int idx,int low,int high,int i,int val,int seg[])
{
if(low==high)
{
seg[idx]=val;
return;
}
int mid=(low+high)/2;
if(i<=mid)update(2*idx+1,low,mid,i,val,seg);
else update(2*idx+2,mid+1,high,i,val,seg);
seg[idx]=min(seg[2*idx+1],seg[2*idx+2]);
}
void solve()
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int seg[4*n];
build(0,0,n-1,arr,seg);
int q;
cin>>q;
while(q--)
{
int type;
cin>>type;
if(type==1)
{
int l,r;
cin>>l>>r;
cout<<query(0,0,n-1,l,r,seg)<<endl;
}
else
{
int idx,val;
cin>>idx>>val;
update(0,0,n-1,idx,val,seg);
arr[idx]=val;
}
}
}
int main()
{
solve();
return 0;
}

You might also like