前缀、差分与哈希状态 · HTML
数学 / 逻辑形态
定义 prefix[0]=0，prefix[i+1]=prefix[i]+a[i]。半开区间 [l,r) 的和为 prefix[r]-prefix[l]。
识别信号
- 对同一静态数组反复查询连续区间和。
- 暴力每次扫描区间造成 O(nq)。
- 聚合运算具有可逆差分，如加法或 XOR。
- 二维矩形查询可由包含排除组合四个二维前缀。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 频繁点更新 | 普通前缀更新一个值要改后续全部；改用 Fenwick 或 segment tree。 |
| 区间最大值 | max 没有可逆减法，不能由两个普通前缀恢复任意区间。 |
核心不变量
prefix[i] 始终表示恰好前 i 个元素 a[0:i] 的聚合；索引 i 是数量而不是原数组元素位置。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 长度 n+1 的 prefix、查询端点 l/r，以及统一的半开区间约定。 |
| Transition | 构建时 prefix[i+1]=prefix[i]+a[i]；查询时右前缀减左前缀。 |
| Frontier / order | 构建前沿从左到右推进；一旦建成，所有区间查询互相独立。 |
Python 骨架
def build_prefix(values):
prefix = [0]
for value in values:
prefix.append(prefix[-1] + value)
return prefix
def range_sum(prefix, left, right):
# Sum over half-open interval [left, right).
if not (0 <= left <= right < len(prefix)):
raise IndexError('invalid range')
return prefix[right] - prefix[left]
正确性思路
- 由递推归纳，prefix[i] 等于 a[0]+…+a[i-1]。
- prefix[r] 包含 [0,l) 与 [l,r)，减去 prefix[l] 正好消去共同前缀。
- 每次查询只访问两个已验证的前缀，因此返回精确区间和。
复杂度
| Time | Space | Parameters |
|---|
| 预处理 O(n)，每次查询 O(1) | O(n) | n 为数组长度，q 次查询总计 O(n+q)。 |
边界条件
- 空区间 l=r 的和为 0。
- 全区间 [0,n) 使用 prefix[n]-prefix[0]。
- 闭区间 [l,r] 必须改写为 prefix[r+1]-prefix[l]。
- 大整数语言中累计和可能溢出。
错误模式
| Pattern | Why it fails / fix |
|---|
| prefix 长度只建 n | 缺少 0 哨兵导致 l=0 特判和大量 off-by-one。 |
| 混用闭/半开区间 | 先写清 [l,r) 或 [l,r]，不要靠记忆套公式。 |
| 动态更新仍重建前缀 | 高频更新下复杂度退化，应换动态区间结构。 |
选择与排除规则
- 静态数组 + 多次可逆区间聚合：前缀。
- 只做一次区间查询：直接扫描可能更省。
- 更新与查询混合：Fenwick/segment tree。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 区间和为 5。 |
| Setup | 值 [3,-1,4,2]，询问半开区间 [1,4)。 |
| Trace | prefix=[0,3,2,6,8]；取 8-3。 |
Recall prompts
我的补充