I am a beginner in Segment Tree implementation , I just learned the algo so now I wanted to do it’s problems.
I picked up this problem from a previous question but I am getting wrong answers. It seems like I might have missed something , can be from the problem statement or the implementation. Please help me in figuring it out. Here’s my code for this spoj problem
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll getmid(ll s, ll e){
return s+(e-s)/2;
}
ll getsumutil(ll *st,ll ss,ll se,ll qs,ll qe,ll index){
if(qs<=ss&&qe>=se)
return st[index];
if(se<qs||ss>qe) return 0;
ll mid=getmid(ss,se);
return getsumutil(st,ss,mid,qs,qe,2*index+1)+getsumutil(st,mid+1,se,qs,qe,2*index+2);
}
ll getsum(ll *st,ll n,ll qs,ll qe){
return getsumutil(st,0,n-1,qs,qe,0);
}
ll constructutil(ll arr[],ll ss,ll se,ll *st,ll si){
if(ss==se){
st[si]=arr[ss];
return arr[ss];
}
ll mid=getmid(ss,se);
st[si]=constructutil(arr,ss,mid,st,si*2+1)+constructutil(arr,mid+1,se,st,si*2+2);
return st[si];
}
ll *construct(ll arr[],ll n){
ll x=(ll)(ceil(log2(n)));
ll max_size=4*x;
ll *st=new ll[max_size];
constructutil(arr,0,n-1,st,0);
return st;
}
main(){
ll n;cin>>n;
ll i;//vector<ll> a(1001);
ll a[4*n];
for(i=0;i<n;i++)cin>>a[i];
ll *st=construct(a,n);
ll m;cin>>m;
while(m--){
ll x,y;
cin>>x>>y;
cout<<getsum(st,n,x,y)<<endl;
}
return 0;
}
And if you happen to know any beginner friendly problems for segment trees implementation , it would be great for me as well as fellow learners.
THANKS IN ADVANCE…