如何快速获取非有序列表指定子区间的最大值？

针对你提到的非有序数值列表频繁查询索引区间最大值的需求，以下两种方案可以将查询时间优化到O(logn)或O(1)，且完全保留原列表顺序：

1. 稀疏表（Sparse Table） #

• 预处理复杂度：O(nlogn)
• 查询复杂度：O(1)
• 适用场景：静态列表（无元素修改需求）
• 实现思路：
  • 预处理阶段，构建一个二维数组st，其中st[k][i]表示从索引i开始，长度为2^k的区间内的最大值。
  • 利用动态规划填充数组：st[0][i]就是原数组的第i个元素；对于k>0，st[k][i] = max(st[k-1][i], st[k-1][i + 2^(k-1)])（确保i + 2^(k-1)不越界）。
  • 查询区间[l, r]时，先计算区间长度len = r - l + 1，取k = floor(log2(len))，然后取max(st[k][l], st[k][r - 2^k + 1])，这两个区间会完全覆盖[l, r]，它们的最大值就是目标结果。

2. 线段树（Segment Tree） #

• 预处理复杂度：O(n)
• 查询复杂度：O(logn)
• 适用场景：静态/动态列表（支持后续元素修改）
• 实现思路：
  • 构建一棵二叉树，每个节点对应原数组的一个区间，节点存储该区间的最大值。叶子节点对应原数组的单个元素，非叶子节点的值由左右子节点的最大值合并得到。
  • 查询区间[l, r]时，递归遍历线段树，合并所有完全落在[l, r]内的节点的最大值，最终得到结果。
  • 如果后续需要修改数组元素，只需更新对应叶子节点，并向上回溯更新父节点的值，时间复杂度也是O(logn)。

补充说明 #

• 如果你的列表完全不需要修改，优先选择稀疏表，它的查询速度更快，实现也相对简洁。
• 若存在未来修改元素的潜在需求，线段树是更灵活的选择，牺牲一点查询速度换来了动态更新能力。

内容的提问来源于stack exchange，提问作者Bobin