How to Implement segment tree over Minimum range query Operation in O(log n)?

Question

give an example.

Answer 1

#include<bits/stdc++.h>
using namespace std;
void constructtree(int segment[],int input[],int low,int high,int pos)
{
    if(low==high)
    {
       segment[pos]=input[low];
       return;
    }
    int mid=(low+high)/2;
    constructtree(segment,input,low,mid,2*pos+1);
    constructtree(segment,input,mid+1,high,2*pos+2);
    segment[pos]=min(segment[2*pos+1],segment[2*pos+2]);
}
int query(int segment[],int low,int high,int ql,int qh,int pos)
{
    if(ql<=low&&qh>=high)
return segment[pos];
if(qh<low||ql>high)
return INT_MAX;
else{
int mid=(low+high)/2;
    return min(query(segment,low,mid,ql,qh,2*pos+1),query(segment,mid+1,high,ql,qh,2*pos+2));
}
}
int main()
{
 int input[]={-1,3,4,0,2,1};
 int segment[20];
constructtree(segment,input,0,5,0);
 cout<<"Enter the range"<<endl;
 int ql,qh;
 cin>>ql>>qh;
 cout<<query(segment,0,5,ql,qh,0);

    return 0;
}