线段树的区间历史最值查询与懒标记下传优化

知识点描述

线段树（Segment Tree）是一种用于高效处理区间查询和区间更新的数据结构。在基础版本中，线段树通常支持区间最值查询（如最大值、最小值）和区间赋值/加法更新。
区间历史最值查询是一种更复杂的操作，它不仅要查询当前区间的某个最值，还要查询在整个更新过程中该区间曾经达到过的历史最值（例如，历史最大值或历史最小值）。
为了高效支持这种查询，需要设计特殊的懒标记（Lazy Propagation），不仅要记录当前待进行的更新，还要记录更新过程中标记的历史最值。
此知识点要求理解如何在线段树中同时维护“当前值”和“历史最值”，并通过复合懒标记实现高效的区间更新与查询。

解题过程（原理与实现步骤）

1. 问题场景与定义

假设我们有一个数组 arr，初始值已知。需要支持两种操作：

• 区间加法更新：对区间 [L, R] 内的每个元素加上一个值 val。
• 区间历史最大值查询：查询区间 [L, R] 内，所有元素在整个操作过程中曾经达到过的最大值（不仅当前值）。

例子：
初始数组：[0, 0, 0, 0]
操作1：区间 [1, 3] 加 5 → 数组变为 [0, 5, 5, 5]，此时历史最大值就是 5。
操作2：区间 [2, 4] 加 -2 → 数组变为 [0, 5, 3, 3]，但历史最大值仍为 5（因为元素 arr[2] 曾经达到过 5，即使现在变为 3）。
查询 [2, 3] 的历史最大值应为 5。

2. 线段树节点设计

每个线段树节点需要存储以下信息：

• cur_max：当前区间最大值。
• his_max：历史区间最大值（即该区间在所有更新过程中达到过的最大值）。
• add_tag：当前待下传的加法懒标记（表示当前区间每个元素应加的值，但尚未下传到子节点）。
• add_his_tag：历史最大加法懒标记（表示在懒标记下传过程中，该区间曾经累积的最大待加值，用于更新子节点的历史最大值）。

为什么需要两个懒标记？
因为区间更新可能多次叠加，我们需要记录“当前累积的更新”和“曾经累积的最大更新”，以便正确更新子节点的历史最大值。

3. 更新操作与懒标记合并

当对一个区间进行加法更新时，我们需要：

1. 更新当前节点的 cur_max 和 his_max：
   • cur_max += val
   • his_max = max(his_max, cur_max) （更新历史最大值）
2. 更新懒标记：
   • add_tag += val
   • add_his_tag = max(add_his_tag, add_tag) （记录历史最大懒标记）

关键点：
在将懒标记下传给子节点时，子节点不仅要应用当前累积的更新，还要根据父节点的历史最大懒标记更新自己的历史最大值。
具体下传过程：

def push_down(node):
    left = node.left
    right = node.right
    # 更新左子节点的历史最大值：考虑左子节点曾经达到的最大值 + 父节点历史最大懒标记
    left.his_max = max(left.his_max, left.cur_max + node.add_his_tag)
    left.cur_max += node.add_tag
    left.add_his_tag = max(left.add_his_tag, left.add_tag + node.add_his_tag)
    left.add_tag += node.add_tag

    # 右子节点同理
    right.his_max = max(right.his_max, right.cur_max + node.add_his_tag)
    right.cur_max += node.add_tag
    right.add_his_tag = max(right.add_his_tag, right.add_tag + node.add_his_tag)
    right.add_tag += node.add_tag

    # 清空父节点懒标记
    node.add_tag = 0
    node.add_his_tag = 0

4. 区间更新与查询过程

• 区间更新：递归找到目标区间，更新节点值并打上懒标记（调用 push_down 保证子节点更新）。
• 区间查询：与普通线段树查询类似，但返回的是节点的 his_max。

5. 时间复杂度

• 建树：O(n)
• 每次更新或查询：O(log n)
  懒标记下传确保操作不会退化到 O(n)。

6. 实例演算

以初始数组 [0, 0, 0, 0] 为例，建立线段树（每个节点存储 (cur_max, his_max)）：

根节点: (0, 0)

操作1：区间 [1, 3] 加 5
递归更新到对应区间，更新后：

根节点: (5, 5)，懒标记 add_tag=5, add_his_tag=5

操作2：区间 [2, 4] 加 -2
下传根节点懒标记到子节点，然后更新区间 [2, 4]。
最终查询 [2, 3] 的历史最大值：

节点 [2,3] 的 his_max = 5

结果为 5。

7. 扩展与变种

• 区间赋值更新：可以类似设计，但懒标记需记录“当前赋值”和“历史最大赋值”。
• 同时支持多种操作（如加法与赋值混合），需要更复杂的懒标记合并逻辑。
• 历史最小值：原理相同，只需维护 cur_min、his_min 和对应的懒标记。

总结

线段树的历史最值查询通过扩展懒标记系统，既记录了当前更新，也记录了更新过程中的极值，从而在 O(log n) 时间内回答历史最值查询。
核心在于设计两个懒标记：一个表示当前累积更新，另一个表示历史最大累积更新，并在下传时正确更新子节点的历史最值。
这种技巧在需要分析“过程最值”的场景（如监控系统峰值、游戏角色属性变化历史）中非常有用。