GSS1: Help needed in approach.

help
c
c-plus-plus
segment-tree
spoj

#1

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*;
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…


#2

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
https://www.codechef.com/problems/MQRY
https://www.codechef.com/problems/SNCHT2