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

Popular posts from this blog

searchKeyword not working in AngularJS filter -

sequelize.js - Sequelize: sort by enum cases -

user interface - how to replace an ongoing process of image capture from another process call over the same ImageLabel in python's GUI TKinter -