线段树通过静态数组构建区间最大值结构，支持O(log n)单次查询、迭代优化、离线批量处理及ZKW内存连续化实现。
一、构建线段树存储区间最大值
线段树是一种二叉树结构，每个节点代表原数组某一区间的最大值。通过自底向上递归合并左右子区间的最大值，可在 O(n) 时间内完成建树，支持后续高效查询。
1、定义线段树节点结构体，包含左端点 l、右端点 r 和存储的最大值 max_val。
2、申请大小为 4 * n 的数组 tree，用于静态存储线段树节点值（避免动态指针开销）。
3、编写 build 函数，参数为当前节点编号 node、区间左边界 l、右边界 r；当 l == r 时，tree[node] = arr[l]；否则递归构建左右子树，并令 tree[node] = max(tree[left_child], tree[right_child])。
4、调用 build(1, 0, n - 1)，以索引 1 为根节点，覆盖整个数组区间 [0, n-1]。
二、单次 RMQ 查询：递归遍历匹配区间
查询任意 [ql, qr] 区间最大值时，从根节点出发，根据当前节点区间与查询区间的重叠关系决定是否进入子树，确保只访问必要路径，时间复杂度为 O(log n)。
1、编写 query 函数，参数为当前节点 node、当前节点覆盖区间 [l, r]、目标查询区间 [ql, qr]。
2、若 [l, r] 与 [ql, qr] 无交集，返回 INT_MIN。
3、若 [l, r] 完全包含于 [ql, qr]，直接返回 tree[node]。
4、否则递归查询左子节点（对应区间 [l, mid]）和右子节点（对应区间 [mid+1, r]），返回二者最大值。
三、单次 RMQ 查询：迭代式下推优化
避免函数调用栈开销，采用显式栈或循环模拟递归过程，通过维护待处理节点及其对应区间元组，减少指令分支预测失败率，提升缓存局部性。
1、使用 std::stack<:tuple int>> 存储待处理项：(node, l, r)。
2、初始压入 (1, 0, n - 1)。
3、初始化 result = INT_MIN。
4、循环弹栈，对每个 (node, l, r) 判断交集关系：无交则跳过；完全包含则 result = max(result, tree[node])；否则压入左右子节点 (2*node, l, mid) 和 (2*node+1, mid+1, r)。
5、循环结束后返回 result。
四、批量 RMQ 查询：离线排序 + 线段树标记更新
当存在大量查询且允许离线处理时，可将所有查询按右端点升序排序，边扩展右边界边更新线段树，使每次查询仅需单点访问根到叶子路径上的最优值，整体复杂度降至 O((n + q) log n)。
1、将所有查询 {ql, qr, idx} 按 qr 升序排列。
2、初始化指针 j = 0，表示当前已处理到原数组位置 j。
3、对每个查询，循环执行 update(1, 0, n-1, j, arr[j]) 并 j++，直到 j > qr。
4、执行 query(1, 0, n-1, ql, qr)，结果存入 ans[idx]。
五、内存连续化优化：ZKW 线段树实现
ZKW 线段树采用堆式数组布局，底层叶节点从索引 N 开始连续存放，父节点为 i/2，无需递归与区间参数传递，所有操作均为位运算与循环，大幅提升常数性能。
1、计算最小 2 的幂 N ≥ n，开辟大小为 2*N 的数组 t。
2、将 arr[i] 赋值给 t[N + i]，i ∈ [0, n)；其余位置设为 INT_MIN。
3、自底向上 for (int i = N - 1; i >= 1; --i) t[i] = max(t[2*i], t[2*i+1])。
4、查询 [l, r] 时，令 l += N, r += N，初始化 res = INT_MIN；while (l
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
