I was trying to solve this problem http://www.spoj.com/problems/GSS1/, after sometime I gave up and googled approach for it, I found this website https://kartikkukreja.wordpress.com/2014/11/09/a-simple-approach-to-segment-trees/ but still not able to understand problem and its solution.Plz help!
I will explain my approach and I will give you my code.
In this problem we need to keep a structure in each node that can help us to determine the answer for a node from its children. The structure that I used is the following:
sum_left — the maximum sum of consecutive elements that contains the leftmost element in the range.
sum_right — the maximum sum of consecutive elements that contains the rightmost element in the range.
sum_max — the answer for the interval.
sum_total — the total sum of the elements in the range.
indicator — flag that tells us whether sum_max=sum_total. That is, the whole interval is the one with maximum sum.
Obviously, for leaf nodes indicator=true and sum_right=sum_left=sum_max=sum_total=[The current element in the array].
For non-leaf nodes:
sum_left=(left child).sum_left
if (left child).indicator=true, then sum_left+=(right child).sum_left
sum_right=(right child).sum_right
if (right child).indicator=true, then sum_right+=(left child).sum_right
sum_total=(left child).sum_total + (right child).sum_total
sum_max=max((left node).sum_max,(right node).sum_max,sum_left,sum_right,sum_total,(left node).sum_right+(right node).sum_left)
My code is here.
Thanks for your reply! Can you explain what is meant by this " Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } "
It means the maximum sum of consecutive elements from the interval [x;y].
For example, let's take the array 1,2,3,-100,5.
Query(1;5) = 6 (1+2+3).
Query(3;5) = 5 (5).
Query(4;4) = -100 (-100).