前缀、差分与哈希状态 · HTML
数学 / 逻辑形态
对闭区间 [l,r] 加 delta：diff[l]+=delta，若 r+1<n 则 diff[r+1]-=delta。最终 a[i]=base[i]+Σ_{j≤i}diff[j]。
识别信号
- 有大量 range add/subtract，最后才读取结果。
- 更新作用在连续区间且增量相同。
- 只关心最终点值、最大覆盖或容量是否超限。
- 逐更新逐位置修改会达到 O(nq)。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 更新后立即查询 | 未积分的 diff 不能直接回答点/区间值；在线混合操作需 Fenwick/segment tree。 |
| 区间赋值 | 覆盖赋值不是简单可叠加增量，端点加减不足以处理覆盖优先级。 |
核心不变量
diff 记录相邻真实值的变化；区间增量在 l 开始生效，并在 r+1 被完全撤销。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 长度 n 或 n+1 的 diff、区间端点、delta，以及最终运行前缀 current。 |
| Transition | 每个更新只写两个事件；所有更新后从左到右 current+=diff[i] 并应用到结果。 |
| Frontier / order | 更新阶段没有逐点前沿；恢复阶段前缀 current 表示所有已开始但尚未结束的区间增量总和。 |
Python 骨架
def apply_range_adds(length, updates):
diff = [0] * (length + 1)
for left, right, delta in updates:
if not (0 <= left <= right < length):
raise IndexError('invalid update')
diff[left] += delta
diff[right + 1] -= delta
result = [0] * length
running = 0
for i in range(length):
running += diff[i]
result[i] = running
return result
正确性思路
- 一次 [l,r] 更新的前缀贡献在 i<l 为 0，在 l≤i≤r 为 delta，在 i>r 又因负事件回到 0。
- 线性叠加使多个更新的 diff 事件可任意顺序累加。
- 最终一次前缀恢复每个位置覆盖它的全部区间增量，故结果正确。
复杂度
| Time | Space | Parameters |
|---|
| O(q+n) | O(n) | q 为更新数，n 为坐标长度；每更新 O(1)，恢复 O(n)。 |
边界条件
- 空长度时更新集合必须为空。
- right=n-1 时用 n+1 哨兵可无分支写 diff[right+1]。
- delta 可为负数。
- 若原数组非零，恢复增量后还需加 base[i]。
错误模式
| Pattern | Why it fails / fix |
|---|
| 忘记 r+1 撤销 | 增量会错误影响区间右侧所有位置。 |
| 闭/半开端点混乱 | 闭区间撤销于 r+1，半开 [l,r) 撤销于 r。 |
| 直接读取 diff[i] | diff 是变化量，必须前缀积分才是点值。 |
选择与排除规则
- 离线批量区间加、最终统一读：差分。
- 在线点查询也可用 Fenwick 的差分思想。
- 在线区间聚合或复杂更新：segment tree。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 增量数组 [0,4,6,6,2]。 |
| Setup | 长度 5；[1,3] 加 4，[2,4] 加 2。 |
| Trace | 事件为 +4@1,-4@4,+2@2,-2@5；前缀恢复。 |
Recall prompts
我的补充