top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+1 vote
219 views
How to Implement segment tree over Minimum range query Operation in O(log n)?
posted May 28, 2016 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes
#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;
}
answer May 28, 2016 by Rajan Paswan
Similar Questions
+1 vote

While reading possible time complexity i found that time complexity O(log log n) exist for some algos,

Can any one explain an example which shows the calculation of the time complexity with O(log log n)

...