iamdumb's blog

Maximum subsegment sum--Segment Trees
By iamdumb, 10 years ago, In English

Hello,i have just started to learn Segment trees and for me to do GSS1 & GSS3 from spoj i have to learn how to calculate Maximum sub-segment sum.Can anybody suggest me some resource where i can get the full information except e-maxx(google translate is making a big mess).Or can anybody explain me here only if you have some time.I don't get why using structure and what's going on ??

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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 C0, C1?

  1. You can do it your self :)

  2. See 1.

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

  4. See 1.

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

Same ideas that were used to support our Segment Tree.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you so much sir. Have you done that question ?can i see your code for this problem(GSS1 or3)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The github link for GSS1 code is available in the quora answer. :) And don't call me sir. Please.

      → Reply