Count sub-arrays whose product is divisible by k

#include<bits/stdc++.h>
using namespace std;
int k;
void build_tree(int*a,int s,int e,int*tree, int index)
{
    if(s>e)
    return;
    
    if(s==e)
    {
        tree[index]=a[s]%k;
        return;
    }
    
    int mid=(s+e)/2;
    build_tree(a,s,mid,tree,2*index);
    build_tree(a,mid+1,e,tree,2*index+1);
    
    tree[index]=((tree[2*index]%k)*(tree[2*index+1]%k))%k;
    return;
  
}

int query(int*tree,int ts,int te,int qs,int qe,int index)
{
    if(ts>qe || te<qs)
       return 1;
       
    if(ts>=qs && te<=qe)
       return tree[index];
       
    int mid=(ts+te)/2;
    int left = query(tree,ts,mid,qs,qe,2*index);
    int right= query(tree,mid+1,te,qs,qe,2*index+1);
    
    return ((left%k)*(right%k))%k;
       
}







int main()
{
    int a[]={6,2,8};
     k=4;
    int n=(sizeof(a)/sizeof(a[0]));
    
    int tree[4*n+1];
    
    build_tree(a,0,n-1,tree,1);
    
    int ans=0;
    
    for(int i=0;i<n;i++)
    {
        int low=i,high=n-1;
        
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(query(tree,0,n-1,i,mid,1)==0)
                high=mid-1;
            else
                low=mid+1;
        }
        
       ans+=n-low; 
        
        
        
    }
    
    
    cout<<ans<<endl;
    return 0;
    
    
    
}