I want to use a minimum segment tree to answer no of elements which are less than k in a specific array range l to r in an unsorted array of integers. In the recursive function query I return the range of given tree element if the tree element lies within the range and also the minimum of this range is greater than k i.e. all the elements are greater than k, and return 0 if tree element points to only one array element and that too is less than k. Please tell me whats wrong with my approach.
Here we take no of elements and no of queries as input n and q, then for next n lines we take the array elements as input. Then for each query we need to answer the no of elements in the range [l,r] that are greater than k.
void buildTree(int a,int s,int e,int tree,int index){
//Base Case
if(s==e){
tree[index]=a[s];
return;
}
//Recursive case
int mid=(s+e)/2;
buildTree(a,s,mid,tree,2index);
buildTree(a,mid+1,e,tree,2index+1);
tree[index]=min(tree[2index],tree[2index+1]);
return;
}
int query(int tree,int ss,int se,int qs,int qe,int k,int index){
//Complete Overlap
if(se==ss&&tree[index]<k)return 0;
if(ss>=qs && se<=qe&& tree[index]>=k)
return se-ss+1;
//No Overlap
if(ss>qe || qs>se)
return 0;
//Partial Overlap
int mid=(ss+se)/2;
int leftAns=query(tree,ss,mid,qs,qe,k,2index);
int rightAns=query(tree,mid+1,se,qs,qe,k,2index+1);
return leftAns+rightAns;
}
void updateNode(int tree,int ss,int se,int i,int update,int index){
//No Overlap
if(i>se||i<ss)
return;
//LeafNode
if(ss==se){
tree[index]=update;
return;
}
//Partial Overlap
int mid=(ss+se)/2;
updateNode(tree,ss,mid,i,update,2index);
updateNode(tree,mid+1,se,i,update,2index+1);
tree[index]=min(tree[2index],tree[2index+1]);
return;
}
int main(){
int n,q;
cin>>n>>q;
int arr[n];
for(int i=0;i<n;i++)cin>>arr[i];
int tree[4*n];
buildTree(a,0,n-1,tree,1);
for(int i=0;i<q;i++){
int l,r,k;
cin>>l>>r>>k;
cout<<query(tree,0,n-1,l-1,r-1,k,1)<<"\n";
}
return 0;
}