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 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…