GSS1: Help needed in approach.

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…

for understanding the segment tree go through the following links


this will you help you to make your code little simpler and plse do proper indentation
and if u still have doubt plse ask

you can try these question on segment tree


1 Like