区间内最大子段和查询（Segment Tree 应用） 题目描述 给定一个整数数组，要求设计一个数据结构，支持以下两种操作： 查询操作 ：给定区间 [L, R] ，返回该区间内的 最大子段和 （即连续子数组的最大和）。 更新操作 ：修改数组中某个位置的值。 例如，数组 [1, -3, 4, 2] 在区间 [0, 3] 的最大子段和为 6 （子数组 [4, 2] 的和）。 解题思路 如果直接对每次查询暴力计算，时间复杂度为 O(n) ，更新为 O(1) ，但多次查询效率低。 我们需要一种能高效处理 动态区间查询 和 单点更新 的方法。这里使用 线段树（Segment Tree） ，但需存储特殊信息以合并区间。 步骤 1：线段树节点设计 每个节点代表一个区间 [l, r] ，存储以下四个值： sum ：区间内所有元素的和。 lmax ：以区间左端点开始的 最大前缀和 。 rmax ：以区间右端点结束的 最大后缀和 。 max ：区间内的 最大子段和 。 例如，区间 [4, 2] 的四个值分别为： sum = 6 lmax = 6 （从 4 开始取整个区间） rmax = 6 （从 2 往前取整个区间） max = 6 步骤 2：合并左右子区间 设当前节点 t ，左孩子 left ，右孩子 right ，则： t.sum = left.sum + right.sum t.lmax = max(left.lmax, left.sum + right.lmax) 要么最大前缀和只在左半区间，要么跨越到右半区间。 t.rmax = max(right.rmax, right.sum + left.rmax) 类似地，最大后缀和可能跨越左右区间。 t.max = max(left.max, right.max, left.rmax + right.lmax) 最大子段和可能完全在左区间、完全在右区间，或跨越中间。 步骤 3：建树 从根节点开始递归分割区间，直到区间长度为 1（叶子节点）。 叶子节点的四个值均等于该位置的元素值。 示例 ：数组 [1, -3, 4, 2] 叶子节点 [0,0] ： sum=1, lmax=1, rmax=1, max=1 叶子节点 [1,1] ： sum=-3, lmax=-3, rmax=-3, max=-3 合并 [0,0] 和 [1,1] 得到 [0,1] ： sum = 1 + (-3) = -2 lmax = max(1, 1 + (-3)) = max(1, -2) = 1 rmax = max(-3, -3 + 1) = max(-3, -2) = -2 max = max(1, -3, 1 + (-3)) = max(1, -3, -2) = 1 继续合并直到根节点。 步骤 4：查询操作 查询区间 [L, R] 时，递归分解区间，若当前节点区间完全包含在 [L, R] 内，则返回该节点的四个值；否则合并左右子区间的结果（合并方法同步骤 2）。 步骤 5：更新操作 从叶子节点开始更新值，并递归向上合并修改父节点的值。 总结 通过线段树存储额外信息，我们实现了： 查询： O(log n) 更新： O(log n) 建树： O(n) 这种方法巧妙利用了 分治思想 和 区间合并规则 ，是动态规划与线段树的结合典型应用。