Range Minimum query using segment tree

                                       http://www.spoj.com/problems/RMQSQ/

                                 

RMQSQ - Range Minimum Query

fistly tree is built , 1st index will keep the minimum of the range (0,n-1). In Built tree  

IF  st==en  i.e singleton  node is there  , then tre[node] will have same value as a[st];

ELSE  node will call its childs 2*node and 2*node+1  with there ranges.  

tre[in]  will keep the minimum of its two childs.

#include<bits/stdc++.h>

using namespace std;

int tre[1000000],a[1000000];

void build_tree(int in,int st,int en)
{
 if(st>en)
        return ;
 if(st==en)
 {
     tre[in]=a[st];
     return ;
 }
 else
 {
     build_tree(2*in,st,(st+en)/2);
     build_tree(2*in+1,(st+en)/2+1,en);
     tre[in]=min(tre[2*in],tre[2*in+1]);
 }
}




int query(int node,int st,int en,int fs,int fe)  /here variable is st and en it is changing in every recursion
{
 if(fe<st || fs>en || fs>fe)        //if st and en is outside
    return INT_MAX;

 if(fs<=st && fe>=en)       // if st and en is inside fs and fe
 {
     return tre[node];
 }
 else
 {
     return min(query(2*node,st,(st+en)/2,fs,fe),query(1+2*node,1+(st+en)/2,en,fs,fe) );
 }
}






int main()
{
 int n,i;
 cin>>n;

  for(i=0;i<n;i++)
  cin>>a[i];

build_tree(1,0,n-1);                 /// tree is to be built and minimum of range (0,n-1) given to 1st index
  int q,l,r;
  cin>>q;
  for(i=0;i<q;i++)
  {
     cin>>l>>r;
 cout<<query(1,0,n-1,l,r)<<endl; / start looking ur range (l,r) from the 1st node of tree whose range                                                                                                  is(0,n-1)
  }
return 0;
}