前缀信息与差分

◎

本节目标

用累计信息快速回答连续区间问题，并用差分把区间修改压缩为端点更新。

前缀和把“到当前位置为止”的信息保存下来，差分数组把“从这里开始变化”的信息保存下来。两者都把连续区间的重复计算改写为少量局部读写。

识别信号

• 反复查询不同连续区间的和、积或计数；
• 需要统计满足某个和的子数组数量，元素可能为负；
• 多次为一个连续区间整体加同一个值；
• 二维矩阵有多次固定内容的区域查询。

问题模型与核心不变量

一维前缀 prefix[i] 表示前 i 个元素的累计信息，因此区间 [left, right] 可以由两个前缀相减得到。计数题中，映射保存已经出现过的前缀及其次数，处理当前前缀时先查询所需历史前缀，再写入当前前缀。

差分 difference[i] 表示位置 i 相比前一位置的变化。给闭区间加值时只在左端加、右端后一位减；最后做一次前缀还原。

通用模板

frequency[0] = 1
prefix = 0
for num in nums:
    prefix += num
    answer += frequency[prefix - target]
    frequency[prefix] += 1

二维查询则在外面补一圈零：sum[r][c] 保存左上角到 (r - 1, c - 1) 的和，查询时使用四项容斥。

模板变体

• 前后缀乘积：先写左侧累计，再从右侧乘回右侧累计；不需要除法。
• 差分更新：记录端点变化，全部更新完成后统一还原。
• 二维前缀：构造时加上上方和左方，减去重复的左上角。

母题序列

按必学顺序完成下列四题：

1. 和为 K 的子数组（必学）：用前缀和频次统计历史前缀。
2. 除了自身以外数组的乘积（必学）：把左、右累计信息分别写入答案。
3. 航班预订统计（必学）：用差分记录区间增量，再前缀还原。
4. 二维区域和检索 - 矩阵不可变（必学）：用二维前缀和完成常数时间查询。

常见误区

• 统计子数组时遗漏空前缀 0，使从下标 0 开始的答案漏计。
• 把当前前缀先写入频次，导致长度为零的区间被误算。
• 差分的减法写在右端而不是右端后一位，混淆闭区间边界。
• 二维容斥漏减左上角，重复计算重叠区域。

迁移方向

区间查询与修改交替出现时，静态前缀和不再足够，需要转向树状数组或线段树；只有连续窗口单调移动时，则优先考虑滑动窗口。