线段树 (带节点更新的范围最大查询)

线段树是竞争性编程和算法问题解决中重要的数据结构。在本次广泛的讨论中，我们将深入探讨线段树，特别关注区间最大值查询 (RMQ) 和节点更新过程。这些过程能够快速查询和更新特定范围内的data，为有效解决各种问题提供了宝贵的工具。

• 线段树是一种层次数据结构，它允许对数组或列表中的区间或片段进行查询和更新操作。树中的每个节点代表数组的一部分，而叶子节点代表单个元素。这种结构能够对指定片段的聚合数据进行高效处理。

最大区间查询 (RMQ)

RMQ 是一个典型的问题，它要求确定数组元素特定范围内的最大值。考虑以下数组 A = [5, 7, 2, 4, 9, 1]。在这种情况下，对于范围 [1, 4] 的 RMQ 查询将返回该范围内的最大值，即 9 (位于索引 4 处)。

节点上的更新操作

节点更新活动包括更改数组元素的值，然后有效地更新线段树以反映这些更改。在 RMQ 的上下文中，这可能涉及更改特定数组元素的值，然后更新线段树以保持一致性。

带节点更新的 RMQ 线段树结构

针对带节点更新的 RMQ 优化的线段树的结构与用于其他基于片段的查询的结构相似。树中的每个节点存储其相关数组片段中的最大值。这种层次结构允许快速遍历和检索指定范围内的最大值。

线段树表示

线段树可以表示为数组。树的节点各自代表原始数组的一个部分。在带节点更新的 RMQ 的情况下，每个节点存储其关联片段内的最大值。根节点代表整个数组，而叶子节点是单个元素。

通常使用数组来实现树，其中

• 根节点由索引 0 表示。
• 节点 i 的左子节点和右子节点分别由索引 2*i + 1 和 2*i + 2 表示。
• 树数组存储每个片段的最大值。

线段树的构建

线段树的构建是一种自底向上的递归技术。构建线段树的步骤如下：

1. 初始化：创建一个足够大的数组 `tree` 来存储线段树的节点。
2. 构建函数
   • 使用递归函数 `build(node, start, end)` 来构建线段树。
   • 对于每个节点 `node`，区间 `[start, end]` 如下：
   • 如果 `start == end`，则将 `tree[node]` 设置为数组中索引为 `start` 的元素。
   • 在所有情况下，计算中间索引 `mid = (start + end) // 2`。
   • 对于左子节点，递归调用 `build(2 * node + 1, start, mid)`。
   • 对于右子节点，递归调用 `build(2 * node + 2, mid + 1, end)`。
   • 用 `tree[2 * node + 1]` 和 `tree[2 * node + 2]` 之间的最大值更新 `tree[node]`。

实施

输出