CODEWITHSUNDEEP
algorithmtree
user4415506
user4415506

Reputation: 109

Merge Function Of Segment Trees

Problem

I came across the above SPOJ problem and the i learn about Segment Tree, I try to understand it well but i could not understand How merge function works ,

Merge Function can have three possibility

  1. Maximum Sum is in the left Node
  2. Maximum Sum is in the right Node
  3. Maximum Sum is Between Left and Right Node.

Then i came across this code for merging:

SegmentTree merge( SegmentTree a , SegmentTree b)
{
    SegmentTree res ;

    res.Sum = a.Sum + b.Sum ;

    res.maxSum = max( max( a.maxSum , b.maxSum ) , (a.suffixSum + b.prefixSum ) ) ;

    res.prefixSum = max( a.prefixSum , a.Sum + b.prefixSum );

    res.suffixSum = max( b.suffixSum , b.Sum + a.suffixSum );

    return res ;
}

sequence that crosses both of the child intervals, which is obtained by subtracting the minimum in the left child from the maximum in the right child Statement Provided Here

Please Help me to understand the above statement i could not understand prefix and suffix sum PLease Help me to understand the Merge Function Of segment Tree

Upvotes: 1

Views: 748

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

Assuming that we have an array with four elements A,B,C,D.

So Segment tree divides it into this structure:

        Max(A,B,C,D)
          /      \
      Max(A,B)   Max(C,D)
       /   \      /   \
     A      B    C     D

  • Ok, so for Max(A,B,C,D), the max sum can be either the max sum in Max(A,B) or Max(C,D) (this is obvious)

  • Or, if A is negative and D is negative, while B and C is not, so the max sum can be B + C,or Max(A,B).suffixSum + Max(C,D).prefixSum.

Note: For a node (L,R) in the segment tree, suffix sum is the max sum segment that starts from x and ends at R with L<= x <= R, and prefix sum is the max sum segment that starts at L and ends at x, with L<= x <= R.

To calculate prefix sum (suffix sum can be done similarly):

  • For example, at node Max(C,D) , so the prefix sum will be Max of (prefix sum in node C, Sum of whole node C + prefix sum in node D). Because the prefix sum must be started at one end, so it should be prefix of the first node, or the whole first node plus the prefix part of the second node.

  • Similarly, for suffix sum, it will be Max of(suffix sum in node D, suffix sum of node C + whole sum of node D).

Hope that it is clear!

Upvotes: 2

Related Questions