c++ - How to find the number of elements divisible by 3 within a range using segment tree?

Question

I am learning the segment tree algorithm and trying to solve problems using it. This problem asks me to output the number of elements divisible by 3 within a given range. I thought my logic is correct but it doesn't output correct results.

If the input array is 4 -9 3 7 1 0 2 and given range is 1-4, it should output 1, since only -9 is divisible by 3.

#include <bits/stdc++.h>
#define mx 100005
typedef long long int ll;
using namespace std;
ll arr[mx];
ll tree[mx*3];

void init(int node, int b, int e){
    if(b == e){
        tree[node] = arr[b];
        return;
    }
    else{
        int Left = node*2;
        int Right = (node*2)+1;
        int mid = (b + e)>>1;

        init(Left, b, mid);
        init(Right, mid+1, e);

        int cnt = 0;
        if(tree[Left]%3 == 0)cnt++;
        if(tree[Right]%3 == 0)cnt++;
        tree[node] = cnt;
    }
}


int divQuery(int node, int b, int e, int i, int j){
    if(i>e || j<b)return;
    if(b>=i && e<=j)return tree[node];

    int Left = node*2;
    int Right = (node*2)+1;
    int mid = (b + e)>>1;

    int data1 = divQuery(Left, b, mid, i, j);
    int data2 = divQuery(Right, mid+1, e, i, j);
    return data1+data2;
}

int main(){
    int n; cin>>n;
    for(int i=1; i<=n; i++)cin>>arr[i];
    // 4 -9 3 7 1 0 2
    init(1,1,n);
    cout<<divQuery(1,1,n,2,4)<<endl;

    return 0;
}

question from:https://stackoverflow.com/questions/65904291/how-to-find-the-number-of-elements-divisible-by-3-within-a-range-using-segment-t

Answer 1

Waitting for answers