You are not logged in. Please login at www.codechef.com to post your questions!

×

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....

asked 30 Aug '15, 03:38

shubham99's gravatar image

2★shubham99
2403932
accept rate: 5%

edited 30 Aug '15, 05:18


for understanding the segment tree go through the following links http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html 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

link

answered 30 Aug '15, 09:22

suman9868's gravatar image

2★suman9868
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,718
×1,911
×1,755
×1,477
×1,135

question asked: 30 Aug '15, 03:38

question was seen: 916 times

last updated: 30 Aug '15, 09:22