In every node of Segment Tree that corresponds some segment from L to R you should store 4 values:

1. max value among prefixes sums of this node (such M that sum(A[L..M]) -> max)

2. max value among suffixes sums of this node (such M that sum(A[M..R]) -> max)

3. max value among all sub-segments sums of this node.

4. just sum(A[L..R])

How to support these values for some node P using pair of its children C₀, C₁?

1. You can do it your self :)

2. See 1.

3. We have 3 cases: our max sub-segment is sub-segment of C₀, or max sub-segment is sub-segment of C₁, or max sub-segment partly contains in C₀ and partly in C₁. So P.ans = max(C₀.ans, C₁.ans, C₀.suff + C₁.pref)

4. See 1.

How to compute answer for some segment [L; R]?

Same ideas that were used to support our Segment Tree.

To Calculate the maximum sum segment(MSS) for any given range we need to calculate what is the MSS for any given range. So assume i am trying to find the information for [l,r] (range l to r of the array) and I already have the info for [l,k] and [k+1,r]. Now the answer for [l,r] could either lie completely in the left or lie completely in the right. The third option is that it lies both in the left and right..

So at each node of the segment tree, we have 3 informations, best sum, prefix_sum and suffix_sum. Best sum is the answer for that range [l,k]. Why do we need the prefix sum and suffix sum? If the answer lies both in my left and right half, then i'd need the best possible suffix sum of my left and best possible prefix sum of my right child. Correct? Thus we keep track of the best prefix sum and best suffix sums for each node. So the best sum of [l,r] is simply the max(best_sum[l,k], best_sum[k+1,r],suffix_sum[l,k]+prefix_sum[k+1,r].

We have found the relation for best_sum given the prefix_sum and suffix_sum of the node's children. Now we need to update the prefix and suffix of the current node for the node's parent. So to calculate the best_prefix sum there are just two possiblites.. Either the prefix of my left child is the best, or the whole of my left child plus the prefix of my right child. Why is this true? prefix_sum of [l,k] (left child) is the best answer for that given range. Now it can only be better if the prefix ends at [k+1,r]. We know the best prefix sum for [k+1,r] //prefix_sum[k+1,r]. So that should be added to the total_sum of [l,k]. Similarly we can do it for suffix sum as well.

I'll add my code for the problem GSS1, a problem in spoj which asks for the same. If it's not clear how we got the best sum refer to this video, which talks about a divide and conquer technique to solve this problem not for ranges but to figure out for the whole array. The segment tree solution was derived from this.

Link: https://www.quora.com/How-do-I-calculate-the-maximum-sub-segment-sum-in-a-segment-tree/answer/Ashwin-Krish