线段树的合并函数

Question

我遇到了上面的 SPOJ 问题，我学习了线段树，我试图很好地理解它，但我无法理解合并函数的工作原理，

合并函数可以有三种可能

最大和在左节点
最大和在正确的节点
最大和在左右节点之间。

然后我遇到了这个合并代码：

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 ;
}

跨越两个子区间的序列，由右子区间的最大值减去左子区间的最小值得到 Statement Provided Here

请帮助我理解上面的语句我无法理解prefix and suffix sum 请帮助我理解段树的合并功能

Answer 1

假设我们有一个包含四个元素 A、B、C、D 的数组。

所以Segment tree将它分为这样的结构：

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

好的，那么对于Max(A,B,C,D)，最大和可以是Max(A,B)中的最大和，也可以是Max(C,D)中的最大和（这个很明显）
或者，如果A为负数，D为负数，而B和C不是，那么最大和可以是B + C，即Max(A,B).suffixSum + Max(C,D).prefixSum。

注：对于线段树中的一个node (L,R)，后缀sum是从x开始的最大和线段并且在R处以L<= x <= R结束，前缀和是在L处开始并在x处结束的最大和段，其中L<= x <= R.

计算前缀和（后缀和可同理）：

例如，在节点 Max(C,D) 处，因此前缀和将为 Max of (prefix sum in node C, Sum of whole node C + prefix sum in node D)。因为前缀和必须从一端开始，所以应该是第一个节点的前缀，或者整个第一个节点加上第二个节点的前缀部分。
同样，对于后缀和，它将是（节点D的后缀和，节点C的后缀和+节点D的总和）的最大值。

希望清楚！

线段树的合并函数

Merge Function Of Segment Trees

algorithm

tree