c++ - Range minimum Query -
this rmq using segment tree. not getting correct output can tell me wrong.
`
#include<iostream> #include<cmath> #define inf 1e9 using namespace std; int get_mid(int a,int b){ return a+(b-a)/2; } int min(int a,int b){ int temp=(a<b)?a:b; return temp; } int get_min_util(int str[],int beg,int end,int l,int r,int i){ if(l<=beg && r>=end) return str[i]; if(l>end || r<beg){ return 0; ////////c1 } int mid=get_mid(beg,end); return (get_min_util(str,beg,mid,l,r,2*i+1),get_min_util(str,mid+1,end,l,r,2*i+2)); } int get_min(int str[],int len,int l,int r){ if(l<0 || r>len-1 || l>r){ return 0; } else return get_min_util(str,0,len-1,l,r,0); } int build_rmq_arr_util(int str[],int beg,int end,int big_arr[],int i){ if(beg==end){ big_arr[i]=str[beg]; return big_arr[i]; } int mid=get_mid(beg,end); big_arr[i]=min(build_rmq_arr_util(str,beg,mid,big_arr,2*i+1),build_rmq_arr_util(str,mid+1,end,big_arr,2*i+2)); return big_arr[i]; } int*bulid_rmq_arr(int str[],int len){ int temp=ceil(log2(len)); temp=2*pow(2,temp)-1; int *big_arr=new int[temp]; build_rmq_arr_util(str,0,len-1,big_arr,0); return big_arr; } void pop(int arr[],int size){ for(int i=0;i<size;i++){ cout<<arr[i]<<" "; } cout<<endl; } int main(){ int str[]={1,2,3,4,5,6}; int len=sizeof(str)/sizeof(int); int *rmq_arr; rmq_arr=bulid_rmq_arr(str,len); //pop(rmq_arr,3*len); cout<<get_min(rmq_arr,len,1,2); } `
output of code:
0
expected output in range 1-2 2 function get_min_util return 0 if condition comment ////////c1 written
problem in get_min_util().it should return infinity when not in range.also have return minimum of left , right child.
int get_min_util(int str[],int beg,int end,int l,int r,int i){ if(l<=beg && r>=end) return str[i]; if(l>end || r<beg){ return inf; ////////c1 } int mid=get_mid(beg,end); return min(get_min_util(str,beg,mid,l,r,2*i+1),get_min_util(str,mid+1,end,l,r,2*i+2)); }
Comments
Post a Comment