区间查询数据结构 · HTML
数学 / 逻辑形态
st[k][i] 为长度 2^k 的摘要；查询用两个可能重叠的最大二次幂块覆盖区间。
识别信号
- 数组构建后不更新
- 查询数量巨大
- 操作幂等
- 可接受 O(n log n) 预处理
- 目标是 O(1) 区间查询
容易误判的相似信号
| Signal | Why it is different |
|---|
| 动态更新 | 单点变化影响许多块，应选 segment tree。 |
| 区间和的重叠两块 | 加法不幂等，会重复计数；使用 prefix sum。 |
核心不变量
st[k][i] 精确表示 [i,i+2^k)；它由两个相邻半块合并而成。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 二维表 st 与 floor(log2(length)) 的 logs 表。 |
| Transition | 构建从短块到长块；查询取 k=floor(log2(r-l))，合并头尾两个 2^k 块。 |
| Frontier / order | 构建按块长度逐层推进；查询直接定位两个覆盖块，没有动态前沿。 |
Python 骨架
class SparseTableMin:
def __init__(self, a):
n = len(a)
self.log = [0] * (n + 1)
for i in range(2, n + 1): self.log[i] = self.log[i//2] + 1
self.st = [a[:]]
k = 1
while 1 << k <= n:
h = 1 << (k-1)
row = [min(self.st[k-1][i], self.st[k-1][i+h])
for i in range(n-(1<<k)+1)]
self.st.append(row); k += 1
def query(self, l, r):
k = self.log[r-l]
return min(self.st[k][l], self.st[k][r-(1<<k)])
正确性思路
- 第 0 层单元素摘要正确。
- 两个正确半块合并成正确长块。
- 所选头尾块覆盖整个查询且不越界。
- 幂等性使重叠元素重复参与不改变结果。
复杂度
| Time | Space | Parameters |
|---|
| 预处理 O(n log n)，查询 O(1) | O(n log n) | n 为数组长度，Q 次总成本 O(n log n+Q) |
边界条件
- 查询必须非空
- n=1 只有第 0 层
- 长度为二次幂时两块重合
- 负值不影响 min/max
- 返回下标时需定平局规则
错误模式
| Pattern | Why it fails / fix |
|---|
| 混淆结合与幂等 | O(1) 重叠覆盖还要求 f(x,x)=x。 |
| log 参数错误 | 应取 r-l。 |
| 尾块起点错误 | 应为 r-2^k。 |
选择与排除规则
- 静态 min/max/gcd 加海量查询：Sparse Table。
- 静态区间和：prefix sum。
- 存在更新：segment tree 或 Fenwick。
- 查询很少时不要过度预处理。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 合并 [1,5) 与 [2,6)，答案为 2。 |
| Scenario | 静态数组 [6,3,8,2,7,5] 查询 [1,6) 最小值。 |
| Walkthrough | 两块虽重叠，但 min 重复处理相同元素无副作用。 |
Recall prompts
我的补充