class Node:
    def __init__(self):
        self.sum = 0   # 区间和
        self.pre = 0   # 最大前缀和
        self.suf = 0   # 最大后缀和
        self.mx = 0    # 最大子段和

线段树的区间最大子段和查询与更新操作详解 题目描述 给定一个长度为 \( n \) 的数组 \( arr \)，我们希望能高效地支持以下两种操作： 查询操作 ：查询任意区间 \([ l, r]\) 的 最大子段和 （即该区间内和最大的连续子数组的和）。 更新操作 ：将某个位置 \( i \) 的值修改为 \( val \)。 要求实现一个数据结构，使得两种操作的时间复杂度都尽可能低（通常目标为 \( O(\log n) \) 级别）。 知识背景 这是一个经典的线段树进阶应用问题， 普通区间和查询 无法直接得到最大子段和，因为最大子段和可能跨越左右子区间。 为了在 \( O(\log n) \) 时间内完成查询与更新，我们需要在线段树的每个节点中维护 四个值 ，并通过合并策略计算父节点的值。 解题过程 步骤一：理解“最大子段和”的性质 对于一个区间，其最大子段和（记作 mx ）的来源有三种可能： 完全位于左子区间。 完全位于右子区间。 横跨左右子区间（即左子区间的最大后缀和 + 右子区间的最大前缀和）。 为了计算横跨情况，我们还需要知道每个区间的： 区间和 （ sum ）：整个区间的元素和。 最大前缀和 （ pre ）：以区间左端点开头的最大连续和。 最大后缀和 （ suf ）：以区间右端点结尾的最大连续和。 步骤二：定义线段树节点结构 每个节点（对应一个区间）存储四个值： 步骤三：合并两个子区间得到父区间 假设左子节点为 left ，右子节点为 right ，则父节点 res 计算如下： 区间和 ： res.sum = left.sum + right.sum 最大前缀和 ： res.pre = max(left.pre, left.sum + right.pre) （要么只用左半边，要么跨到右半边） 最大后缀和 ： res.suf = max(right.suf, right.sum + left.suf) 最大子段和 ： res.mx = max(left.mx, right.mx, left.suf + right.pre) （三种情况取最大） 例子 ： 数组 [3, -1, 2, 4] 左子区间 [3, -1] ： sum=2, pre=3, suf=2, mx=3 （子数组 [3] ） 右子区间 [2, 4] ： sum=6, pre=6, suf=6, mx=6 （子数组 [2,4] ） 合并后： sum = 2+6=8 pre = max(3, 2+6)=max(3,8)=8 suf = max(6, 6+2)=max(6,8)=8 mx = max(3, 6, 2+6)=max(3,6,8)=8 （对应子数组 [3,-1,2,4] 的和） 步骤四：建树（初始化） 递归地将数组分成两半，直到叶子节点。 叶子节点： sum=pre=suf=mx=arr[i] （如果允许空子数组，需考虑负数，但通常最大子段和至少包含一个元素，所以直接取该值）。 自底向上合并子节点信息。 时间复杂度 ：\( O(n) \)，每个节点计算一次。 步骤五：点更新 从根节点递归到目标叶子节点，更新其值。 回溯时重新合并路径上所有节点的四个值。 时间复杂度 ：\( O(\log n) \)，只更新一条路径。 步骤六：区间查询 查询区间可能跨越多个节点，需要合并多个节点的信息： 如果当前节点区间完全在查询区间内，直接返回该节点的四个值。 如果只在一侧，递归该侧。 如果跨越左右，分别查询左右，然后合并两个结果（合并方法同步骤三）。 注意 ：合并时需要临时节点存储合并结果。 举例说明 数组： arr = [1, -3, 5, 2] 建树后，根节点表示区间 [0,3] ： 左子区间 [0,1] （值 [1,-3] ）： sum=-2, pre=1, suf=1, mx=1 右子区间 [2,3] （值 [5,2] ）： sum=7, pre=7, suf=7, mx=7 合并后： sum = -2+7=5 pre = max(1, -2+7)=max(1,5)=5 suf = max(7, 7+(-2))=max(7,5)=7 mx = max(1, 7, 1+7)=max(1,7,8)=8 （对应子数组 [5,2] 和 1 不连续，但注意这里 1 来自左子区间的后缀和？更正： left.suf=1 ， right.pre=7 ， 1+7=8 对应子数组 [1,-3,5,2] 不对，因为 -3 会减少和。实际上最大子段和是 [5,2]=7 。我们检查计算：左子区间 [1,-3] 的最大后缀和是 max(-3, 1+(-3))? 不， suf 定义为以右端点结尾的最大连续和，对于 [1,-3] ，右端点是 -3 ，以 -3 结尾的连续子数组有 [-3] 和 [1,-3] ，和分别是 -3 和 -2 ，最大值是 -2 ？不对， -2 比 -3 大，但 -2 对应子数组 [1,-3] 。但 [1,-3] 的右端点是 -3 ，所以 suf 应该是 -2 。上面例子中我假设了 suf=1 是错的，应重新计算。 重新计算叶子 ： 叶子 [1] ： sum=1, pre=1, suf=1, mx=1 叶子 [-3] ： sum=-3, pre=-3, suf=-3, mx=-3 合并为区间 [1,-3] ： sum=1+(-3)=-2 pre=max(1, 1+(-3))=max(1,-2)=1 suf=max(-3, -3+1)=max(-3,-2)=-2 mx=max(1, -3, 1+(-3))=max(1,-3,-2)=1 所以左子区间正确值： sum=-2, pre=1, suf=-2, mx=1 右子区间 [5,2] ： 叶子 [5] ： sum=5, pre=5, suf=5, mx=5 叶子 [2] ： sum=2, pre=2, suf=2, mx=2 合并： sum=7 pre=max(5, 5+2)=7 suf=max(2, 2+5)=7 mx=max(5, 2, 5+2)=7 右子区间： sum=7, pre=7, suf=7, mx=7 合并根节点： sum = -2+7=5 pre = max(left.pre, left.sum+right.pre) = max(1, -2+7)=max(1,5)=5 suf = max(right.suf, right.sum+left.suf) = max(7, 7+(-2))=max(7,5)=7 mx = max(left.mx, right.mx, left.suf+right.pre) = max(1, 7, (-2)+7) = max(1,7,5)=7 最大子段和是 7，对应右子区间的 [5,2] 。正确。 查询区间 [0,2] （值 [1,-3,5] ）： 左子区间 [0,1] 如上： sum=-2, pre=1, suf=-2, mx=1 右子区间 [2,2] （叶子 5 ）： sum=5, pre=5, suf=5, mx=5 合并： sum=3 pre=max(1, -2+5)=max(1,3)=3 suf=max(5, 5+(-2))=max(5,3)=5 mx=max(1, 5, (-2)+5)=max(1,5,3)=5 结果 5 对应子数组 [5] （其实是 [1,-3,5] 中最大连续和是 5）。 总结 通过维护 sum, pre, suf, mx 四个值，线段树可以在 \( O(\log n) \) 时间内处理 区间最大子段和 的查询与点更新，是线段树处理复杂区间合并问题的典型例子。