Whats wrong with this code for max query in segmenrt tree.
#include
using namespace std ;
void build_tree(int *arr , int **tree , int ss , int se , int index)
{
//Base Case
if(ss == se)
{
tree[index][0] = 1;
tree[index][1] = arr[ss];
return ;
}
//Recursive case
int mid = (ss + se)/2;
build_tree(arr,tree,ss,mid,2*index);
build_tree(arr,tree,mid+1,se,2*index+1);
int size_left = tree[2*index][0];
int size_right = tree[2*index+1][0];
int i = 1 ;
int j = 1 ;
tree[index][0] = 0;
int k = 1 ;
while(i<=size_left && j<=size_right)
{
if(tree[2*index][i] < tree[2*index+1][j])
{
tree[index][0]++;
tree[index][k] = tree[2*index][i];
i++;
k++;
}
else
{
tree[index][0]++;
tree[index][k] = tree[2*index+1][j];
j++;
k++;
}
}
while(i<= size_left)
{
tree[index][0]++;
tree[index][k] = tree[2*index][i];
i++;
k++;
}
while(j<= size_right)
{
tree[index][0]++;
tree[index][k] = tree[2*index+1][j];
j++;
k++;
}
return ;
}
int query(int **tree, int l, int r , int k , int ss , int se , int index)
{
//No Overlap
if(ss > r || se < l)
{
return 0;
}
//complete overlap
if(ss >= l && se <= r)
{
int size = tree[index][0];
int arr[size];
for(int i = 0 ; i < size ; i++)
{
arr[i] = tree[index][i+1];
}
auto itr = lower_bound(arr,arr+size,k);
int num = itr - arr ;
return (size - num);
}
int mid = (ss + se)/2;
int smalloutput1 = query(tree,l,r,k,ss,mid,2*index);
int smalloutput2 = query(tree,l,r,k,mid+1,se,2*index+1);
return smalloutput1 + smalloutput2 ;
}
int main()
{
int n ;
cin >> n ;
int arr[n+1];
for(int i = 1 ; i <= n ; i++)
{
cin >> arr[i];
}
int **tree = new int*[4*n+1];
for(int i = 1 ; i < 4*n+1 ; i++)
{
tree[i] = new int[n+1];
for(int j = 0 ; j <= n ; j++ )
{
tree[i][j] = 0;
}
}
build_tree(arr,tree,1,n,1);
int q ;
cin >> q ;
while(q--)
{
int l , r , k;
cin >> l >> r >> k ;
cout << query(tree,l,r,k,1,n,1) << endl;
}
for(int i = 0 ; i < 4*n+1 ; i++)
{
delete [] tree[i];
}
delete [] tree;
}