前缀和与差分
前缀和与差分都不复杂，却经常藏在一道题真正的第一步里。
前缀和把一段区间的信息提前累积起来，适合处理大量静态查询；差分只记录相邻位置的变化，适合一次完成大量区间修改。它们看起来方向相反，实际上互为逆运算：对原数组做差分，再求一次前缀和，就能回到原数组。
这一篇从一维前缀和开始，接着整理权值前缀和、二阶前缀和、二维前缀和以及一维、二维差分。正文不依赖配图，重点放在公式、边界和例题中的转换过程。
一维前缀和
给定数组$a_1,a_2,\ldots,a_n$，定义前缀和数组$s$：
$$
s_i=\sum_{j=1}^{i}a_j
$$
规定$s_0=0$，递推式就是：
$$
s_i=s_{i-1}+a_i
$$
因此区间$[l,r]$的和可以拆成“前$r$个数”减去“前$l-1$个数”：
$$
\sum_{i=l}^{r}a_i=s_r-s_{l-1}
$$
预处理代码只有一行：
1 | for (int i = 1; i <= n; i++) { cin >> a[i]; s[i] = s[i - 1] + a[i]; } |
查询同样只有一行：
1 | i64 query(int l, int r) { return s[r] - s[l - 1]; } |
建立前缀和需要$O(n)$时间，每次区间查询只需要$O(1)$。额外空间为$O(n)$。
前缀和并不只用于数字求和。只要能把每个位置转成一个贡献值，就可以累积。例如统计字符串中某种相邻字符出现多少次，可以令满足条件的位置贡献$1$，其余位置贡献$0$；统计区间内偶数个数、合法位置数量也是同样的做法。
这里最容易写错的是下标。本文统一使用从$1$开始的闭区间$[l,r]$，因此答案是 s[r]-s[l-1]。如果题目使用从$0$开始的下标或者左闭右开区间，应该先确定前缀数组到底统计了哪些位置，再写减法，不能直接套公式。
权值前缀和与二阶前缀和
权值前缀和
普通前缀和维护$a_i$的累加，权值前缀和则给每个位置乘上一个与下标有关的系数。最常见的定义是：
$$
w_i=\sum_{j=1}^{i}j\cdot a_j
$$
于是区间$[l,r]$的权值和为：
$$
\sum_{i=l}^{r}i\cdot a_i=w_r-w_{l-1}
$$
代码和普通前缀和几乎完全相同：
1 | for (int i = 1; i <= n; i++) { |
为什么会出现$i\cdot a_i$？通常是因为$a_i$在答案中出现了$i$次。
例如把所有以位置$r$结尾的子段全部列出。$a_1$只会出现在$[1,r]$中，$a_2$会出现在$[1,r]$和$[2,r]$中，$a_i$一共出现在$i$个子段里。因此这些子段的总和为：
$$
\sum_{l=1}^{r}\sum_{j=l}^{r}a_j
=\sum_{j=1}^{r}j\cdot a_j
=w_r
$$
更一般地，只要某个位置的贡献系数能够写成关于$i$的一次式，就可以拆成普通前缀和与权值前缀和。例如：
$$
\sum_{i=l}^{r}(x-i+1)a_i
=(x+1)(s_r-s_{l-1})-(w_r-w_{l-1})
$$
这里的$x$在一次查询中是固定值。看到“每个数出现次数不同，而且次数与位置成一次关系”时，就应该想到同时维护$s_i$与$w_i$。
需要注意，权值前缀和与权值树状数组不是同一个概念。前者是给$a_i$乘上下标等系数；后者通常把数值或排名作为下标，维护每个数出现了多少次。
二阶前缀和
如果再对普通前缀和$s$求一次前缀和，得到：
$$
t_i=\sum_{k=1}^{i}s_k
$$
这就是二阶前缀和。展开每个$s_k$：
$$
\begin{aligned}
t_i
&=a_1+(a_1+a_2)+\cdots+(a_1+a_2+\cdots+a_i)\\
&=\sum_{j=1}^{i}(i-j+1)a_j
\end{aligned}
$$
$a_j$从$s_j$开始一直出现在$s_i$中，一共出现$i-j+1$次。继续整理可得：
$$
t_i=(i+1)s_i-w_i
$$
所以二阶前缀和与权值前缀和并不是同一个数组。在普通前缀和$s$已知时，二者可以通过上式互相换算。
如果需要查询$s_l+s_{l+1}+\cdots+s_r$，直接使用：
$$
\sum_{i=l}^{r}s_i=t_r-t_{l-1}
$$
如果要求从$l$开始、分别以$l,l+1,\ldots,r$结尾的所有子段之和，则每一段为$s_i-s_{l-1}$，答案为：
$$
(t_r-t_{l-1})-(r-l+1)s_{l-1}
$$
二阶前缀和也解释了双树状数组中的公式。设$d$是$a$的差分数组，原数组前$x$项的和就是差分前缀和的前缀和：
$$
\sum_{i=1}^{x}a_i
=(x+1)\sum_{i=1}^{x}d_i-\sum_{i=1}^{x}i\cdot d_i
$$
因此区间修改、区间查询需要分别维护$d_i$与$i\cdot d_i$。树状数组只是把这里的静态前缀和换成了可以动态修改的前缀和。
二维前缀和
一维前缀和把区间变成两个前缀之差，二维前缀和做的是同一件事，只是查询对象从线段变成了矩形。
定义$s_{i,j}$表示左上角$(1,1)$到右下角$(i,j)$这个矩形内的元素和。加入$a_{i,j}$时，上方矩形与左侧矩形会重复计算左上部分，所以需要减去一次：
$$
s_{i,j}=a_{i,j}+s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}
$$
查询左上角$(x_1,y_1)$、右下角$(x_2,y_2)$的闭矩形，同样使用容斥：
$$
\begin{aligned}
q={}&s_{x_2,y_2}-s_{x_1-1,y_2}\\
&-s_{x_2,y_1-1}+s_{x_1-1,y_1-1}
\end{aligned}
$$
前两次减法去掉矩形上方和左侧，多减掉的左上角需要补回来。
1 | for (int i = 1; i <= n; i++) { |
建立二维前缀和需要$O(nm)$时间，每次矩形查询为$O(1)$，额外空间为$O(nm)$。
二维前缀和仍然依赖第$0$行和第$0$列作为空边界。数组至少要开到$(n+1)\times(m+1)$，并保证这些边界初始为$0$。如果原坐标可能从$0$开始，可以整体向右下平移一格，避免在每次查询时特判负下标。
差分
一维差分
定义差分数组$d$：
$$
d_i=a_i-a_{i-1}
$$
规定$a_0=0$，那么对$d$求前缀和就能还原$a$：
$$
a_i=\sum_{j=1}^{i}d_j
$$
如果要让区间$[l,r]$中的每个数增加$k$，区间内部相邻两项都增加了$k$，它们之间的差没有变化。真正需要修改的只有两个边界：
$$
d_l\gets d_l+k
$$
$$
d_{r+1}\gets d_{r+1}-k
$$
完成全部修改以后，求一次前缀和即可得到最终数组：
1 | for (int i = 1; i <= n; i++) a[i] = a[i - 1] + d[i]; |
每次区间修改只需要$O(1)$，最后还原数组需要$O(n)$。
普通差分更适合“先完成全部区间修改，最后统一输出或处理”的离线场景。如果修改与查询交错出现，尚未还原的差分数组不能直接回答任意区间查询，此时通常需要树状数组或线段树。
二维差分
二维差分把“矩形整体增加”转换成四个角的修改。
让闭矩形$(x_1,y_1)$到$(x_2,y_2)$全部增加$k$：
$$
\begin{aligned}
d_{x_1,y_1}&\gets d_{x_1,y_1}+k\\
d_{x_2+1,y_1}&\gets d_{x_2+1,y_1}-k\\
d_{x_1,y_2+1}&\gets d_{x_1,y_2+1}-k\\
d_{x_2+1,y_2+1}&\gets d_{x_2+1,y_2+1}+k
\end{aligned}
$$
前两个位置控制竖直方向的开始与结束，后两个位置再处理水平方向。所有修改完成以后，对$d$求二维前缀和：
$$
d_{i,j}\gets d_{i,j}+d_{i-1,j}+d_{i,j-1}-d_{i-1,j-1}
$$
此时$d_{i,j}$就是位置$(i,j)$最终增加的总量。
一维与二维的关系可以简单整理为：
| 维度 | 前缀和擅长的操作 | 差分擅长的操作 | 还原方式 |
|---|---|---|---|
| 一维 | 静态区间查询 | 区间修改 | 一次前缀和 |
| 二维 | 静态矩形查询 | 矩形修改 | 二维前缀和 |
例题与典型应用
下面七道题按照使用方式排列。前四道先把基础模型写熟，后三道再处理二维修改、贡献次数和连续累加。
| 题目 | 核心方法 | 需要注意的地方 |
|---|---|---|
| 洛谷 P8218 求区间和 | 一维前缀和 | 使用 i64 保存答案 |
| AtCoder ABC122 C GeT AC | 贡献前缀和 | 相邻字符的右端点范围 |
| 洛谷 P2280 激光炸弹 | 二维前缀和 | 坐标整体平移一格 |
| AtCoder ABC035 C オセロ | 一维差分 | 翻转次数只看奇偶性 |
| 洛谷 P3397 地毯 | 二维差分 | 四个角的正负号 |
| Codeforces 276C Maximum Sum | 差分与贪心 | 价值和使用次数同序配对 |
| Codeforces 1355C Count Triangles | 差分与两次前缀和 | 统计和大于$z$的数对 |
例题一：洛谷 P8218 求区间和
题目链接：洛谷 P8218 求区间和
给定长度为$n$的正整数序列和$m$个区间，分别求每个闭区间$[l,r]$的元素和。
这是前缀和最直接的使用方式。先建立$s_i$，每次输出$s_r-s_{l-1}$即可。
虽然单个$a_i$不大，但是区间和可能超过 int。把前缀和数组声明为 i64 更稳妥。
点击展开完整代码
1 | /* Fufffh */ |
预处理时间为$O(n)$，每次查询为$O(1)$，空间复杂度为$O(n)$。
例题二：AtCoder ABC122 C GeT AC
给定一个只含 A、C、G、T 的字符串。每次询问子串$[l,r]$中有多少个连续的 AC。
令$c_i$表示位置$i-1$和$i$是否组成 AC：成立时为$1$，否则为$0$。再对$c$建立前缀和$s$。
一个完全位于$[l,r]$中的 AC，右端点只能位于$[l+1,r]$。如果$s_i$统计右端点不超过$i$的数量，答案就是：
$$
s_r-s_l
$$
这里减去的是$s_l$而不是$s_{l-1}$。因为右端点恰好为$l$的 AC 会跨出查询区间左边界，同样不能计入。
点击展开完整代码
1 | /* Fufffh */ |
预处理时间为$O(n)$，每次查询为$O(1)$，空间复杂度为$O(n)$。
例题三：洛谷 P2280 激光炸弹
题目链接：洛谷 P2280 激光炸弹
平面上有若干目标，每个目标具有一定价值。选择一个边长固定、边与坐标轴平行的正方形，求内部目标的最大价值和。同一坐标可能出现多个目标。
坐标范围不超过$5000$，可以直接建立二维网格。先把同一坐标的价值累加，再求二维前缀和，最后枚举每个边长为$k$的正方形。
原坐标可能等于$0$。为了保留第$0$行和第$0$列作为空边界，读入时把$x,y$都增加$1$：
1 | s[x + 1][y + 1] += v; |
枚举正方形右下角$(i,j)$时，覆盖的网格范围为$(i-k,i]\times(j-k,j]$，价值和为：
$$
s_{i,j}-s_{i-k,j}-s_{i,j-k}+s_{i-k,j-k}
$$
点击展开完整代码
1 | /* Fufffh */ |
设坐标边界为$V$，时间复杂度为$O(V^2)$，空间复杂度为$O(V^2)$。这里$V=5001$，全局数组大约占用$100$ MB，不能放在函数栈中。
例题四：AtCoder ABC035 C オセロ
题目链接：AtCoder ABC035 C オセロ
有$n$枚初始均为$0$的棋子。每次把区间$[l,r]$内的棋子全部翻转，完成$q$次操作后输出最终的$01$串。
一次翻转相当于让区间内每个位置的翻转次数增加$1$。使用差分数组记录：
1 | d[l]++; |
最后求前缀和，得到每个位置一共被翻转了多少次。偶数次仍然为$0$，奇数次变成$1$，因此只需要输出 d[i]&1。
点击展开完整代码
1 | /* Fufffh */ |
总时间复杂度为$O(n+q)$，空间复杂度为$O(n)$。
例题五：洛谷 P3397 地毯
题目链接：洛谷 P3397 地毯
在$n\times n$的格子上依次铺设$m$张矩形地毯，输出每个格子最终被覆盖了多少次。
如果对每张地毯内部的所有格子逐一增加$1$，最坏复杂度会达到$O(mn^2)$。二维差分只修改四个角，每张地毯可以在$O(1)$时间内记录。
对于左上角$(x_1,y_1)$、右下角$(x_2,y_2)$的闭矩形：
1 | d[x1][y1]++; |
全部地毯处理完成以后，求一次二维前缀和，当前值就是该格子的覆盖次数。
点击展开完整代码
1 | /* Fufffh */ |
总时间复杂度为$O(m+n^2)$，空间复杂度为$O(n^2)$。
例题六：Codeforces 276C Little Girl and Maximum Sum
题目链接：Codeforces 276C Little Girl and Maximum Sum
给定一个数组和$q$个区间。可以在回答询问以前任意重排数组，要求所有区间和的总和最大。
与其逐个计算区间，不如先统计每个位置一共会被询问多少次。设位置$i$被覆盖$c_i$次，那么所有询问答案之和就是：
$$
\sum_{i=1}^{n}a_i c_i
$$
每个询问$[l,r]$都让$c_l,c_{l+1},\ldots,c_r$增加$1$，正好可以使用差分数组在$O(1)$时间记录。
接下来需要决定如何重排$a$。为了让乘积和最大，应当把最大的$a_i$放在使用次数最多的位置，第二大的放在第二多的位置。因此分别排序$a$与$c$，按照相同顺序配对即可。
点击展开完整代码
1 | /* Fufffh */ |
统计覆盖次数需要$O(n+q)$，排序需要$O(n\log n)$，总时间复杂度为$O(n\log n+q)$，空间复杂度为$O(n)$。
例题七：Codeforces 1355C Count Triangles
题目链接：Codeforces 1355C Count Triangles
给定$a\le b\le c\le d$，统计满足下面范围的非退化三角形数量：
$$
a\le x\le b\le y\le c\le z\le d
$$
由于$x\le y\le z$已经由取值范围保证，三角形不等式中只需要检查：
$$
x+y>z
$$
固定$x$以后，$y$在$[b,c]$内变化，和$s=x+y$会依次取遍区间$[x+b,x+c]$，每个值恰好对应一个$(x,y)$。
建立数组$cnt$，让$cnt_s$表示有多少对$(x,y)$满足$x+y=s$。对于每个$x$，不必枚举所有$y$，只要对$[x+b,x+c]$整体增加$1$：
1 | cnt[x + b]++; |
第一次求前缀和以后，$cnt_s$变成和恰好等于$s$的数对数量。再求一次前缀和，$cnt_s$就变成和不超过$s$的数对数量。
记全部$(x,y)$的数量为$total$。对于固定的$z$，合法数对数量就是：
$$
total-cnt_z
$$
这道题中的“两次前缀和”有不同职责：第一次还原差分，第二次累计答案。写代码时最好先说清楚数组在每一步表示什么，否则很容易多做或少做一次累加。
点击展开完整代码
1 | /* Fufffh */ |
令$V=\max(b+c,d)$，数组长度、时间复杂度和空间复杂度均为$O(V)$。
总结与常见问题
应该使用哪一种？
- 数组不再修改，需要大量区间查询：使用前缀和；
- 每个位置的贡献次数与下标有关：考虑普通前缀和与权值前缀和；
- 需要查询若干段前缀和的总和：建立二阶前缀和；
- 静态矩形查询：使用二维前缀和；
- 先完成大量区间修改，最后统一得到数组：使用差分；
- 先完成大量矩形修改，最后统一得到网格：使用二维差分；
- 修改和查询在线交错出现：继续考虑树状数组或线段树。
常见错误
1. 忘记预留第$0$项
前缀和查询需要访问$s_{l-1}$。当$l=1$时会访问$s_0$，因此数组必须多开一格，并让$s_0=0$。
2. 使用 int 保存区间和
即使每个$a_i$都能放进 int，$n$个数相加、位置权值$i\cdot a_i$以及答案中的乘积仍然可能溢出。涉及累加值时优先检查是否需要 i64。
3. 差分的右端点少加$1$
闭区间$[l,r]$增加$k$，结束位置是$r+1$：
1 | d[l] += k; |
如果把结束位置误写成$r$，位置$r$本身就不会得到这次修改。
4. 二维容斥的符号写反
无论二维前缀查询还是二维差分修改，都可以先从一维思考：一个方向开始、一个方向结束。不要只背四个位置，先确定每个位置影响的是哪一块区域。
5. 把普通差分当成在线数据结构
差分数组能够快速记录修改，但在重新求前缀和以前，$d_i$并不是$a_i$。修改后立刻查询任意区间时，普通差分通常不够用。
6. 不清楚连续两次前缀和的含义
第一次前缀和可能是在还原差分，第二次才是在统计累计数量。每做一次累加，都应当重新写清楚数组当前保存的内容。
复杂度分析
| 方法 | 预处理或还原 | 单次操作 | 空间复杂度 |
|---|---|---|---|
| 一维前缀和 | $O(n)$ | 区间查询$O(1)$ | $O(n)$ |
| 权值或二阶前缀和 | $O(n)$ | 区间查询$O(1)$ | $O(n)$ |
| 二维前缀和 | $O(nm)$ | 矩形查询$O(1)$ | $O(nm)$ |
| 一维差分 | 还原$O(n)$ | 区间修改$O(1)$ | $O(n)$ |
| 二维差分 | 还原$O(nm)$ | 矩形修改$O(1)$ | $O(nm)$ |
