# Spoj GSS1 problem **URL:** \ **Category:** general\ **Tags:** segment-tree\ **Created:** [April 27, 2017, 2:37am UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506 "2017-04-27T02:37:47Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![anno](https://discuss.codechef.com/user_avatar/discuss.codechef.com/anno/32/3653_2.png) [@anno](https://discuss.codechef.com/u/anno)\ **Post date:** [April 27, 2017, 2:37am UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/1 "2017-04-27T02:37:47Z")
I have been trying to understand the solution of [GSS1][1] problem from last 2 days but still not been able to get why are we maintaining the suffixsum and prefixsum of every node. here is the link to the ```auto [2]. can you please explain me the code from line 36 to 48. i have already searched a lot on google but still not been able to get it. please help. [1]: http://www.spoj.com/problems/GSS1/ [2]: http://ideone.com/UgPrJT ``` ---
**Author:** ![neilit1992](https://discuss.codechef.com/user_avatar/discuss.codechef.com/neilit1992/32/6769_2.png) [@neilit1992](https://discuss.codechef.com/u/neilit1992)\ **Post date:** [April 27, 2017, 6:42am UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/2 "2017-04-27T06:42:22Z")
[Code Gyan](http://ayurjain.blogspot.in/?m=1) This is a blog by ayur jain, It is well explained and better to understand what is happening in the code. In GSS1, few of the things you need to consider are best left sum, best right sum, best sum and sum - code by ayur jain [Qq25J5 - Online C++ Compiler & Debugging Tool - Ideone.com](http://ideone.com/Qq25J5) PS i solved this problem after going through his editorial ---
**Author:** ![anon85470456](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon85470456](https://discuss.codechef.com/u/anon85470456)\ **Post date:** [April 27, 2017, 8:56am UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/3 "2017-04-27T08:56:55Z")
Here’s another similar question regarding GSS1 problem : [Please Check the solution to SPOJ GSS1 problem. - general - CodeChef Discuss](https://discuss.codechef.com/questions/94192/please-check-the-solution-to-spoj-gss1-problem) You might look into the code here : [https://github.com/Shraeyas/SPOJ-Solutions/blob/master/gss1.cpp](https://github.com/Shraeyas/SPOJ-Solutions/blob/master/gss1.cpp) ---
**Author:** ![kodeerder](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@kodeerder](https://discuss.codechef.com/u/kodeerder)\ **Post date:** [April 27, 2017, 10:09am UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/4 "2017-04-27T10:09:02Z")
**Codechef: [Crazy Malvika discovers Crazy Fibonacci function](https://www.codechef.com/problems/CHN08)** Asking questions on a new thread without enough karma is impermissible here, so I can’t. Please look into the question. I read the [CHN08 - Editorial](https://discuss.codechef.com/questions/78914/chn08-editorial), but I still can’t understand enough of it. ---
**Author:** ![neilit1992](https://discuss.codechef.com/user_avatar/discuss.codechef.com/neilit1992/32/6769_2.png) [@neilit1992](https://discuss.codechef.com/u/neilit1992)\ **Post date:** [April 27, 2017, 2:31pm UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/5 "2017-04-27T14:31:55Z")
@anno In an array prefix sum comes from left subtree and suffix sum comes from right subtree, therefore to calculate the best sum we need store max(max(A.best,B.best),A.suffix+B.prefix) Go through the image I’ve calculated what is actually happening in code We take tree[n].prefix=max(tree[2_n+1].prefix,tree[2_n+1].sum+B.prefix) because max sum can be in left sub tree or left subtree + left subtree of right sub tree and vice versa for tree[n] suffix ![alt text](https://discuss.codechef.com/upfiles/33d72814-9a8a-4117-a443-215a9e0ee9e7.jpg) This pic is just to depict the meaning, you can paper run the program on these values to better understand the codes. ![alt text](https://discuss.codechef.com/upfiles/b216ed4d-d21d-4a1d-b118-baa22b9c8847_1.jpg) ---
**Author:** ![mathecodician](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mathecodician/32/29889_2.png) [@mathecodician](https://discuss.codechef.com/u/mathecodician)\ **Post date:** [April 27, 2017, 3:44pm UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/6 "2017-04-27T15:44:39Z")
Can somebody tell why I am getting WA? My code - [zUnx5g - Online IDE & Debugging Tool - Ideone.com](http://ideone.com/zUnx5g) ---
**Author:** ![meooow](https://discuss.codechef.com/user_avatar/discuss.codechef.com/meooow/32/97120_2.png) [@meooow](https://discuss.codechef.com/u/meooow)\ **Post date:** [April 27, 2017, 4:54pm UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/7 "2017-04-27T16:54:39Z")
Here’s my attempt at explaining the approach. The problem is the **maximum sum subarray** problem, which you want to solve by a divide and conquer approach, which is what a segment tree does. For a given range A, you split it into two pieces, the left half L and the right half R. Naturally the maximum sum subarray in A can lie either 1) completely in L, or lie 2) completely in R, or 3) cross over from L to R. Solve recursively for the two halves. We get the maximum sum subarrays for the left half as L.maxsum and the right half as R.maxsum, and now we know the first 2 of the 3 options just like that \*snaps fingers\* 😛 How do we get the third option? A range that extends from L to R can be broken into a suffix of L and a prefix of R. So if we know the maximum suffix sum in L as L.suffixsum and the maximum prefix sum in R as R.prefixsum, the sum of those 2 values will give us the maximum sum subarray extending from L to R, which covers option 3. So we get ``` tree[index].maxsum = max(max(tree[2\*index+1].maxsum, tree[2\*index+2].maxsum), tree[2\*index+1].suffixsum + tree[2\*index+2].prefixsum); ``` Now since we have incorporated 2 new values (prefixsum and suffixsum), the parent range of A will also require these from A. So now we need to calculate A.prefixsum and A.suffixsum. The maximum sum prefix of A can be 1) the maximum sum prefix of L, or 2) cover the whole of L and extend into R. Option 1 is simply L.prefixsum, and option 2 is \sum L + R.prefixsum. Similarly, the maximum sum suffix of A is either R.suffixsum or \sum R + L.suffixsum. So now it seems we need another value to represent a range, which is the sum of that range. So we have ``` tree[index].prefixsum = max(tree[2\*index+1].prefixsum, tree[2\*index+1].sum + tree[2\*index+2].prefixsum); tree[index].suffixsum = max(tree[2\*index+2].suffixsum, tree[2\*index+2].sum + tree[2\*index+1].suffixsum); ``` And for the sum it is simply ``` tree[index].sum = tree[2\*index+1].sum + tree[2\*index+2].sum; ``` Well, that covers the whole thing, I hope it is clear why we require the 4 values in one node of the segment tree. Also you can see that the calculation of `tree[index].maxsum` in the link you provided can be simplified as I have described above. Feel free to ask if anything is not clear 🙂 ---
**Author:** ![anon85470456](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon85470456](https://discuss.codechef.com/u/anon85470456)\ **Post date:** [April 27, 2017, 9:25pm UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/8 "2017-04-27T21:25:20Z")
@mathecodician it gives TLE on SPOJ, How come you get WA? ![alt text](https://discuss.codechef.com/upfiles/err.png) ---
**Author:** ![anon85470456](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon85470456](https://discuss.codechef.com/u/anon85470456)\ **Post date:** [April 27, 2017, 9:35pm UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/9 "2017-04-27T21:35:43Z")
@mathecodician Here’s the accepted code : [kUy1h1 - Online C++ Compiler & Debugging Tool - Ideone.com](http://ideone.com/kUy1h1) Simply changed those vectors to array and added cin.tie(0) for fast IO. ---
**Author:** ![anno](https://discuss.codechef.com/user_avatar/discuss.codechef.com/anno/32/3653_2.png) [@anno](https://discuss.codechef.com/u/anno)\ **Post date:** [April 28, 2017, 1:12am UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/10 "2017-04-28T01:12:09Z")
@meooow @neilit1992 for the ans of any query we are checking if (l \> mid) or if (r \<= mid) why are we doing this ``` int mid = (start+end)/2; if (l > mid) return query(2*index+2, mid+1, end, l, r); if (r <= mid) return query(2*index+1, start, mid, l, r); node left = query(2*index+1,start,mid,l,r); node right = query(2*index+2,mid+1,end,l,r); ``` ---
**Author:** ![anon85470456](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon85470456](https://discuss.codechef.com/u/anon85470456)\ **Post date:** [May 2, 2017, 8:41am UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/11 "2017-05-02T08:41:28Z")
@anno you can have a look on this video tutorial to clear your doubts regarding Segment Trees. Here’s the [Link](https://www.youtube.com/watch?v=ZBHKZF5w4YU) Now as far as your question is concerned, l and r are the intervals in which we have to make query on the segment tree. Also start to mid and mid+1 to end are the two segments in which we have divided the current interval(i.e. start to end). Now start to mid will be in the left child of current node and mid+1 to end will be in the right child of current node. Now it should be clear that in your code if l\>mid, then we don’t have to query on the left child of current node, that’s why we simply moved to position 2\*pos+2 (right child). Similarly, if r\<=mid then we can straightaway move to the left child of current node, that is why you did set the position there to 2\*pos+1 Hope this helps. If you have any other doubts please comment below. 🙂 ---
**Author:** ![arpit728](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arpit728/32/4830_2.png) [@arpit728](https://discuss.codechef.com/u/arpit728)\ **Post date:** [May 3, 2018, 6:52pm UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/12 "2018-05-03T18:52:19Z")
@meooow @neilit1992 @anno I am getting TLE, can you please look into it. > **[GSS1 - Pastebin.com](https://pastebin.com/jyuhAm22)** > > Pastebin.com is the number one paste tool since 2002. Pastebin is a website where you can store text online for a set period of time. ---
**Author:** ![may55](https://discuss.codechef.com/user_avatar/discuss.codechef.com/may55/32/3653_2.png) [@may55](https://discuss.codechef.com/u/may55)\ **Post date:** [October 22, 2018, 4:05am UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/13 "2018-10-22T04:05:07Z")
The **best** explanation I got on Google.[link](http://strangeonehere.blogspot.com/2018/03/spoj-gss1.html) ---
**Author:** ![not\_found99](https://discuss.codechef.com/user_avatar/discuss.codechef.com/not_found99/32/208155_2.png) [@not\_found99](https://discuss.codechef.com/u/not_found99)\ **Post date:** [February 25, 2019, 4:48pm UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/14 "2019-02-25T16:48:30Z")
#include\ using namespace std; typedef long long int ll; ll arr[50005]; struct Tree{ ll pre,su,tot,bst; }tree[200005]; void build\_tree(ll node,ll a,ll b) { if(a==b) { tree[node].pre=arr[a]; tree[node].su=arr[a]; tree[node].tot=arr[a]; tree[node].bst=arr[a]; return; } ll mid=(a+b)\>\>1; build\_tree(node_2,a,mid); build\_tree(node_2+1,mid+1,b); tree[node].pre=max(tree[node_2].pre,tree[node_2].tot+tree[node_2+1].pre); tree[node].su=max(tree[node_2+1].su,tree[node_2+1].tot+tree[node_2].su); tree[node].tot=tree[node_2].tot+tree[node_2+1].tot; tree[node].bst=max(tree[node_2].su+tree[node_2+1].pre,max(tree[node_2].bst,tree[node_2+1].bst)); } Tree query\_tree(ll node, ll a ,ll b, ll i,ll j) { Tree t; if(a\>b||a\>j||b\=i&&b\<=j) return tree[node]; ll mid=(a+b)\>\>1; Tree q1=query\_tree(node_2,a,mid,i,j); Tree q2=query\_tree(node_2+1,mid+1,b,i,j); t.pre=max(q1.pre,q1.tot+q2.pre); t.su=max(q2.su,q2.tot+q1.su); t.tot=q1.tot+q2.tot; t.bst=max(q1.su+q2.pre,max(q1.bst,q2.bst)); return t; } int main() { int n; cin\>\>n; for(int i=1;i\<=n;i++) cin\>\>arr[i]; build\_tree(1,1,n); ll q; cin\>\>q; while(q–) { ll l,r; cin\>\>l\>\>r; Tree a=query\_tree(1,1,n,l,r); cout\<\ **Author:** ![anno](https://discuss.codechef.com/user_avatar/discuss.codechef.com/anno/32/3653_2.png) [@anno](https://discuss.codechef.com/u/anno)\ **Post date:** [April 27, 2017, 11:24am UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/15 "2017-04-27T11:24:59Z") Can you please explain me concept of prefixsum and sufixsum for every node?? Means why and how are we maintaining those two sums ---
**Author:** ![vijju123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vijju123/32/195207_2.png) [@vijju123](https://discuss.codechef.com/u/vijju123)\ **Post date:** [April 27, 2017, 11:43am UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/16 "2017-04-27T11:43:46Z")
Delete this post and ask in a new thread now. 🙂 ---
**Author:** ![neilit1992](https://discuss.codechef.com/user_avatar/discuss.codechef.com/neilit1992/32/6769_2.png) [@neilit1992](https://discuss.codechef.com/u/neilit1992)\ **Post date:** [April 27, 2017, 2:35pm UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/17 "2017-04-27T14:35:33Z")
@anno I’ve uploaded pics, prefix sum is max of ( (sum of left subtree + left node sum of right subtree) and left node sum of left subtree) suffix sum is max of (( sum of right subtree+right node sum of left subtree) and right node sum of right sub tree) ---
**Author:** ![anon85470456](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon85470456](https://discuss.codechef.com/u/anon85470456)\ **Post date:** [April 27, 2017, 4:01pm UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/18 "2017-04-27T16:01:44Z")
@mathecodician can you please explain your approach? ---
**Author:** ![mathecodician](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mathecodician/32/29889_2.png) [@mathecodician](https://discuss.codechef.com/u/mathecodician)\ **Post date:** [April 27, 2017, 4:19pm UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/19 "2017-04-27T16:19:50Z")
It’s just the normal approach but iterative instead of recursive. ---
**Author:** ![anon85470456](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon85470456](https://discuss.codechef.com/u/anon85470456)\ **Post date:** [April 27, 2017, 4:56pm UTC](https://discuss.codechef.com/t/spoj-gss1-problem/14506/20 "2017-04-27T16:56:46Z")
It is failing for this case 10 -1 9 2 6 -4 3 5 2 -6 1 1 4 7 The answer should be 8 while your code gives 6. [Next page](https://discuss.codechef.com/t/spoj-gss1-problem/14506.md?page=2)