前缀和与差分数组

前缀和与差分数组解决的是同一类核心问题：区间信息太多，不能每次都从头扫到尾。前缀和适合“多次查询区间和”，差分数组适合“多次修改区间后再统一统计结果”。这两种方法经常一起出现，因为差分做完修改以后，最后一步本身就是一轮前缀还原。

学习目标

识别哪些题目适合用一维或二维前缀和。
识别哪些题目更适合先做差分标记，再统一还原。
学会把“区间和查询”“覆盖统计”“峰值扫描”“矩形求和”落到固定模板。
学会在实现里处理好下标、边界和 64 位整数。

什么情况下该想到前缀和

如果题目同时满足下面几条，优先检查能不能上前缀和：

原始数据是数组、时间轴、网格或矩阵。
有大量区间查询，且原数组在查询阶段不再变化。
每次查询都要求求和、计数、覆盖量或矩形和。
朴素做法会对每个查询再扫一遍，复杂度明显偏高。

对应到题库：

一维前缀和

定义

设原数组为 a[1..n]，定义：

pre[i] = a[1] + a[2] + ... + a[i]

并约定 pre[0] = 0。

那么闭区间 [l, r] 的和就是：

sum(l, r) = pre[r] - pre[l - 1]

为什么有效

pre[r] 包含了前 r 个元素，pre[l - 1] 包含了前 l - 1 个元素。两者相减，刚好只剩下 a[l..r]。

代码骨架

pre = [0] * (n + 1)
for i in range(1, n + 1):
    pre[i] = pre[i - 1] + a[i]

segment_sum = pre[r] - pre[l - 1]

常见用途

多次区间求和
固定长度窗口和
区间平均值、区间人数、区间销量
前缀差值进一步推导最值

二维前缀和

定义

设矩阵为 grid[1..n][1..m]，定义：

pre[i][j] = (1,1) 到 (i,j) 这个左上矩形内的总和

转移公式是：

pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i][j]

子矩形求和

查询矩形 (r1, c1) 到 (r2, c2) 的和时，用容斥：

sum = pre[r2][c2] - pre[r1 - 1][c2] - pre[r2][c1 - 1] + pre[r1 - 1][c1 - 1]

为什么一定要画图理解

二维前缀和最容易错在“重复减去了一块区域”。手算一次左上矩形、上边矩形、左边矩形和重叠矩形的关系，比死背公式更稳。

什么情况下该想到差分数组

如果题目同时满足下面几条，优先检查能不能上差分：

有很多区间加一、区间减一或区间统一增加某个值的操作。
不要求每次修改之后立刻回答查询。
更关心最后每个位置的覆盖次数、活跃次数、占用量或库存变化。

对应到题库：

一维差分数组

定义

对原数组 a 定义差分数组 diff：

diff[1] = a[1]
diff[i] = a[i] - a[i - 1]

但在竞赛题里，更常见的是直接把 diff 当成“区间操作的记账本”。

闭区间加法模板

若要把 [l, r] 上的每个值都加上 x：

diff[l] += x
diff[r + 1] -= x

最后统一做一遍前缀和，就能还原每个位置的真实值。

为什么这么做

你不是在每个位置都加 x，而是在 l 位置记下“从这里开始多了 x”，在 r + 1 位置记下“从这里开始不再多 x”。前缀恢复时，这种影响会自动向后传播。

前缀和与差分的组合题

很多题不是二选一，而是两者一起出现：

先用差分记录很多区间修改。
做一遍前缀和，还原每个位置的真实值。
再顺手统计最大值、峰值首次出现位置、覆盖长度、连续区间等附加信息。

这正是 s1-jh-06、s2-jh-07、s3-jh-06 这类题的标准结构。

实现时最容易出错的地方

下标体系不统一

题面是 1-based，你代码却按 0-based 硬套。
前缀和公式写的是 pre[r] - pre[l - 1]，代码却没给 pre[0] 留位置。

`r + 1` 越界

差分数组通常要开到 n + 2 或 m + 2。
闭区间 [l, r] 的结束标记写在 r + 1，不是 r。

整型范围不够

一维、二维前缀和都可能超出 32 位整数。
Python 问题不大，C++ 至少要用 long long。

统计附加指标时顺序错了

还原当前值和统计最值、覆盖长度、首峰位置时，顺序必须固定：

先做前缀恢复出当前位置真实值。
再根据真实值更新答案。

不要还没恢复就拿 diff[i] 当作当前位置结果。

与其他方法的边界

如果数组会动态修改并且要在线查询，单纯前缀和就不够，通常要考虑树状数组或线段树。
如果查询不是求和，而是区间最值，前缀和不一定直接适用。
如果题目只需要一个固定长度窗口最值，也可能用滑动窗口更直接。

题库中的典型观察点

`s1-jh-05`

看点是“一维前缀和 + 多次查询 + 额外统计最大单点”。

`s2-jh-05`

看点是“二维前缀和 + 容斥 + 多矩形查询”。

`s2-jh-07`

看点是“差分还原分钟覆盖数，再统计覆盖总长度和峰值”。

`s3-jh-06`

看点是“差分得到每天开放数，再顺扫合并正区间”。

训练建议

每写一道前缀和题，都先在纸上写出 pre[0] 的含义。
每写一道差分题，都强制自己先写一句：这题是闭区间还是半开区间。
对二维前缀和，先手算一个 3x3 小矩阵，确认容斥方向没错再写代码。
如果答案不对，先打印前缀数组或还原后的数组，不要直接怀疑最终公式。