前缀和与差分都不复杂,却经常藏在一道题真正的第一步里。

前缀和把一段区间的信息提前累积起来,适合处理大量静态查询;差分只记录相邻位置的变化,适合一次完成大量区间修改。它们看起来方向相反,实际上互为逆运算:对原数组做差分,再求一次前缀和,就能回到原数组。

这一篇从一维前缀和开始,接着整理权值前缀和、二阶前缀和、二维前缀和以及一维、二维差分。正文不依赖配图,重点放在公式、边界和例题中的转换过程。

一维前缀和

给定数组a1,a2,…,ana_1,a_2,\ldots,a_n,定义前缀和数组ss:

si=∑j=1iajs_i=\sum_{j=1}^{i}a_j

规定s0=0s_0=0,递推式就是:

si=si−1+ais_i=s_{i-1}+a_i

因此区间[l,r][l,r]的和可以拆成“前rr个数”减去“前l−1l-1个数”:

∑i=lrai=sr−sl−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(n)时间,每次区间查询只需要O(1)O(1)。额外空间为O(n)O(n)。

前缀和并不只用于数字求和。只要能把每个位置转成一个贡献值,就可以累积。例如统计字符串中某种相邻字符出现多少次,可以令满足条件的位置贡献11,其余位置贡献00;统计区间内偶数个数、合法位置数量也是同样的做法。

这里最容易写错的是下标。本文统一使用从11开始的闭区间[l,r][l,r],因此答案是 s[r]-s[l-1]。如果题目使用从00开始的下标或者左闭右开区间,应该先确定前缀数组到底统计了哪些位置,再写减法,不能直接套公式。

权值前缀和与二阶前缀和

权值前缀和

普通前缀和维护aia_i的累加,权值前缀和则给每个位置乘上一个与下标有关的系数。最常见的定义是:

wi=∑j=1ij⋅ajw_i=\sum_{j=1}^{i}j\cdot a_j

于是区间[l,r][l,r]的权值和为:

∑i=lri⋅ai=wr−wl−1\sum_{i=l}^{r}i\cdot a_i=w_r-w_{l-1}

代码和普通前缀和几乎完全相同:

1
2
3
4
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i];
w[i] = w[i - 1] + 1LL * i * a[i];
}

为什么会出现i⋅aii\cdot a_i?通常是因为aia_i在答案中出现了ii次。

例如把所有以位置rr结尾的子段全部列出。a1a_1只会出现在[1,r][1,r]中,a2a_2会出现在[1,r][1,r]和[2,r][2,r]中,aia_i一共出现在ii个子段里。因此这些子段的总和为:

∑l=1r∑j=lraj=∑j=1rj⋅aj=wr\sum_{l=1}^{r}\sum_{j=l}^{r}a_j =\sum_{j=1}^{r}j\cdot a_j =w_r

更一般地,只要某个位置的贡献系数能够写成关于ii的一次式,就可以拆成普通前缀和与权值前缀和。例如:

∑i=lr(x−i+1)ai=(x+1)(sr−sl−1)−(wr−wl−1)\sum_{i=l}^{r}(x-i+1)a_i =(x+1)(s_r-s_{l-1})-(w_r-w_{l-1})

这里的xx在一次查询中是固定值。看到“每个数出现次数不同,而且次数与位置成一次关系”时,就应该想到同时维护sis_i与wiw_i。

需要注意,权值前缀和与权值树状数组不是同一个概念。前者是给aia_i乘上下标等系数;后者通常把数值或排名作为下标,维护每个数出现了多少次。

二阶前缀和

如果再对普通前缀和ss求一次前缀和,得到:

ti=∑k=1iskt_i=\sum_{k=1}^{i}s_k

这就是二阶前缀和。展开每个sks_k:

ti=a1+(a1+a2)+⋯+(a1+a2+⋯+ai)=∑j=1i(i−j+1)aj\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}

aja_j从sjs_j开始一直出现在sis_i中,一共出现i−j+1i-j+1次。继续整理可得:

ti=(i+1)si−wit_i=(i+1)s_i-w_i

所以二阶前缀和与权值前缀和并不是同一个数组。在普通前缀和ss已知时,二者可以通过上式互相换算。

如果需要查询sl+sl+1+⋯+srs_l+s_{l+1}+\cdots+s_r,直接使用:

∑i=lrsi=tr−tl−1\sum_{i=l}^{r}s_i=t_r-t_{l-1}

如果要求从ll开始、分别以l,l+1,…,rl,l+1,\ldots,r结尾的所有子段之和,则每一段为si−sl−1s_i-s_{l-1},答案为:

(tr−tl−1)−(r−l+1)sl−1(t_r-t_{l-1})-(r-l+1)s_{l-1}

二阶前缀和也解释了双树状数组中的公式。设dd是aa的差分数组,原数组前xx项的和就是差分前缀和的前缀和:

∑i=1xai=(x+1)∑i=1xdi−∑i=1xi⋅di\sum_{i=1}^{x}a_i =(x+1)\sum_{i=1}^{x}d_i-\sum_{i=1}^{x}i\cdot d_i

因此区间修改、区间查询需要分别维护did_i与i⋅dii\cdot d_i。树状数组只是把这里的静态前缀和换成了可以动态修改的前缀和。

二维前缀和

一维前缀和把区间变成两个前缀之差,二维前缀和做的是同一件事,只是查询对象从线段变成了矩形。

定义si,js_{i,j}表示左上角(1,1)(1,1)到右下角(i,j)(i,j)这个矩形内的元素和。加入ai,ja_{i,j}时,上方矩形与左侧矩形会重复计算左上部分,所以需要减去一次:

si,j=ai,j+si−1,j+si,j−1−si−1,j−1s_{i,j}=a_{i,j}+s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}

查询左上角(x1,y1)(x_1,y_1)、右下角(x2,y2)(x_2,y_2)的闭矩形,同样使用容斥:

q=sx2,y2−sx1−1,y2−sx2,y1−1+sx1−1,y1−1\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
2
3
4
5
6
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}

建立二维前缀和需要O(nm)O(nm)时间,每次矩形查询为O(1)O(1),额外空间为O(nm)O(nm)。

二维前缀和仍然依赖第00行和第00列作为空边界。数组至少要开到(n+1)×(m+1)(n+1)\times(m+1),并保证这些边界初始为00。如果原坐标可能从00开始,可以整体向右下平移一格,避免在每次查询时特判负下标。

差分

一维差分

定义差分数组dd:

di=ai−ai−1d_i=a_i-a_{i-1}

规定a0=0a_0=0,那么对dd求前缀和就能还原aa:

ai=∑j=1idja_i=\sum_{j=1}^{i}d_j

如果要让区间[l,r][l,r]中的每个数增加kk,区间内部相邻两项都增加了kk,它们之间的差没有变化。真正需要修改的只有两个边界:

dl←dl+kd_l\gets d_l+k

dr+1←dr+1−kd_{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(1),最后还原数组需要O(n)O(n)。

普通差分更适合“先完成全部区间修改,最后统一输出或处理”的离线场景。如果修改与查询交错出现,尚未还原的差分数组不能直接回答任意区间查询,此时通常需要树状数组或线段树。

二维差分

二维差分把“矩形整体增加”转换成四个角的修改。

让闭矩形(x1,y1)(x_1,y_1)到(x2,y2)(x_2,y_2)全部增加kk:

dx1,y1←dx1,y1+kdx2+1,y1←dx2+1,y1−kdx1,y2+1←dx1,y2+1−kdx2+1,y2+1←dx2+1,y2+1+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}

前两个位置控制竖直方向的开始与结束,后两个位置再处理水平方向。所有修改完成以后,对dd求二维前缀和:

di,j←di,j+di−1,j+di,j−1−di−1,j−1d_{i,j}\gets d_{i,j}+d_{i-1,j}+d_{i,j-1}-d_{i-1,j-1}

此时di,jd_{i,j}就是位置(i,j)(i,j)最终增加的总量。

一维与二维的关系可以简单整理为:

维度 前缀和擅长的操作 差分擅长的操作 还原方式
一维 静态区间查询 区间修改 一次前缀和
二维 静态矩形查询 矩形修改 二维前缀和

例题与典型应用

下面七道题按照使用方式排列。前四道先把基础模型写熟,后三道再处理二维修改、贡献次数和连续累加。

题目 核心方法 需要注意的地方
洛谷 P8218 求区间和 一维前缀和 使用 i64 保存答案
AtCoder ABC122 C GeT AC 贡献前缀和 相邻字符的右端点范围
洛谷 P2280 激光炸弹 二维前缀和 坐标整体平移一格
AtCoder ABC035 C オセロ 一维差分 翻转次数只看奇偶性
洛谷 P3397 地毯 二维差分 四个角的正负号
Codeforces 276C Maximum Sum 差分与贪心 价值和使用次数同序配对
Codeforces 1355C Count Triangles 差分与两次前缀和 统计和大于zz的数对

例题一:洛谷 P8218 求区间和

题目链接:洛谷 P8218 求区间和

给定长度为nn的正整数序列和mm个区间,分别求每个闭区间[l,r][l,r]的元素和。

这是前缀和最直接的使用方式。先建立sis_i,每次输出sr−sl−1s_r-s_{l-1}即可。

虽然单个aia_i不大,但是区间和可能超过 int。把前缀和数组声明为 i64 更稳妥。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n;
cin >> n;
vector<i64> s(n + 1);
for (int i = 1; i <= n; i++) { i64 x; cin >> x; s[i] = s[i - 1] + x; }
int m;
cin >> m;
while (m--) {
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << '\n';
}
return 0;
}

预处理时间为O(n)O(n),每次查询为O(1)O(1),空间复杂度为O(n)O(n)。

例题二:AtCoder ABC122 C GeT AC

题目链接:AtCoder ABC122 C GeT AC

给定一个只含 A、C、G、T 的字符串。每次询问子串[l,r][l,r]中有多少个连续的 AC。

令cic_i表示位置i−1i-1和ii是否组成 AC:成立时为11,否则为00。再对cc建立前缀和ss。

一个完全位于[l,r][l,r]中的 AC,右端点只能位于[l+1,r][l+1,r]。如果sis_i统计右端点不超过ii的数量,答案就是:

sr−sls_r-s_l

这里减去的是sls_l而不是sl−1s_{l-1}。因为右端点恰好为ll的 AC 会跨出查询区间左边界,同样不能计入。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, q;
string str;
cin >> n >> q >> str;
str = " " + str;
vector<int> s(n + 1);
for (int i = 2; i <= n; i++) s[i] = s[i - 1] + (str[i - 1] == 'A' && str[i] == 'C');
while (q--) {
int l, r;
cin >> l >> r;
cout << s[r] - s[l] << '\n';
}
return 0;
}

预处理时间为O(n)O(n),每次查询为O(1)O(1),空间复杂度为O(n)O(n)。

例题三:洛谷 P2280 激光炸弹

题目链接:洛谷 P2280 激光炸弹

平面上有若干目标,每个目标具有一定价值。选择一个边长固定、边与坐标轴平行的正方形,求内部目标的最大价值和。同一坐标可能出现多个目标。

坐标范围不超过50005000,可以直接建立二维网格。先把同一坐标的价值累加,再求二维前缀和,最后枚举每个边长为kk的正方形。

原坐标可能等于00。为了保留第00行和第00列作为空边界,读入时把x,yx,y都增加11:

1
s[x + 1][y + 1] += v;

枚举正方形右下角(i,j)(i,j)时,覆盖的网格范围为(i−k,i]×(j−k,j](i-k,i]\times(j-k,j],价值和为:

si,j−si−k,j−si,j−k+si−k,j−ks_{i,j}-s_{i-k,j}-s_{i,j-k}+s_{i-k,j-k}

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

constexpr int V = 5001;
int s[V + 2][V + 2];

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int x, y, v;
cin >> x >> y >> v;
s[x + 1][y + 1] += v;
}
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

int ans = 0;
for (int i = k; i <= V; i++) {
for (int j = k; j <= V; j++) {
int cur = s[i][j] - s[i - k][j] - s[i][j - k] + s[i - k][j - k];
ans = max(ans, cur);
}
}
cout << ans << '\n';
return 0;
}

设坐标边界为VV,时间复杂度为O(V2)O(V^2),空间复杂度为O(V2)O(V^2)。这里V=5001V=5001,全局数组大约占用100100 MB,不能放在函数栈中。

例题四:AtCoder ABC035 C オセロ

题目链接:AtCoder ABC035 C オセロ

有nn枚初始均为00的棋子。每次把区间[l,r][l,r]内的棋子全部翻转,完成qq次操作后输出最终的0101串。

一次翻转相当于让区间内每个位置的翻转次数增加11。使用差分数组记录:

1
2
d[l]++;
d[r + 1]--;

最后求前缀和,得到每个位置一共被翻转了多少次。偶数次仍然为00,奇数次变成11,因此只需要输出 d[i]&1。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, q;
cin >> n >> q;
vector<int> d(n + 2);
while (q--) {
int l, r;
cin >> l >> r;
d[l]++;
d[r + 1]--;
}
for (int i = 1; i <= n; i++) { d[i] += d[i - 1]; cout << (d[i] & 1); }
cout << '\n';
return 0;
}

总时间复杂度为O(n+q)O(n+q),空间复杂度为O(n)O(n)。

例题五:洛谷 P3397 地毯

题目链接:洛谷 P3397 地毯

在n×nn\times n的格子上依次铺设mm张矩形地毯,输出每个格子最终被覆盖了多少次。

如果对每张地毯内部的所有格子逐一增加11,最坏复杂度会达到O(mn2)O(mn^2)。二维差分只修改四个角,每张地毯可以在O(1)O(1)时间内记录。

对于左上角(x1,y1)(x_1,y_1)、右下角(x2,y2)(x_2,y_2)的闭矩形:

1
2
3
4
d[x1][y1]++;
d[x2 + 1][y1]--;
d[x1][y2 + 1]--;
d[x2 + 1][y2 + 1]++;

全部地毯处理完成以后,求一次二维前缀和,当前值就是该格子的覆盖次数。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m;
cin >> n >> m;
vector<vector<int>> d(n + 2, vector<int>(n + 2));
while (m--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
d[x1][y1]++;
d[x2 + 1][y1]--;
d[x1][y2 + 1]--;
d[x2 + 1][y2 + 1]++;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
cout << d[i][j] << " \n"[j == n];
}
}
return 0;
}

总时间复杂度为O(m+n2)O(m+n^2),空间复杂度为O(n2)O(n^2)。

例题六:Codeforces 276C Little Girl and Maximum Sum

题目链接:Codeforces 276C Little Girl and Maximum Sum

给定一个数组和qq个区间。可以在回答询问以前任意重排数组,要求所有区间和的总和最大。

与其逐个计算区间,不如先统计每个位置一共会被询问多少次。设位置ii被覆盖cic_i次,那么所有询问答案之和就是:

∑i=1naici\sum_{i=1}^{n}a_i c_i

每个询问[l,r][l,r]都让cl,cl+1,…,crc_l,c_{l+1},\ldots,c_r增加11,正好可以使用差分数组在O(1)O(1)时间记录。

接下来需要决定如何重排aa。为了让乘积和最大,应当把最大的aia_i放在使用次数最多的位置,第二大的放在第二多的位置。因此分别排序aa与cc,按照相同顺序配对即可。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, q;
cin >> n >> q;
vector<i64> a(n), d(n + 2);
for (i64 &x : a) cin >> x;
while (q--) {
int l, r;
cin >> l >> r;
d[l]++;
d[r + 1]--;
}
for (int i = 1; i <= n; i++) d[i] += d[i - 1];
sort(a.begin(), a.end());
sort(d.begin() + 1, d.begin() + n + 1);

i64 ans = 0;
for (int i = 1; i <= n; i++) ans += a[i - 1] * d[i];
cout << ans << '\n';
return 0;
}

统计覆盖次数需要O(n+q)O(n+q),排序需要O(nlog⁡n)O(n\log n),总时间复杂度为O(nlog⁡n+q)O(n\log n+q),空间复杂度为O(n)O(n)。

例题七:Codeforces 1355C Count Triangles

题目链接:Codeforces 1355C Count Triangles

给定a≤b≤c≤da\le b\le c\le d,统计满足下面范围的非退化三角形数量:

a≤x≤b≤y≤c≤z≤da\le x\le b\le y\le c\le z\le d

由于x≤y≤zx\le y\le z已经由取值范围保证,三角形不等式中只需要检查:

x+y>zx+y>z

固定xx以后,yy在[b,c][b,c]内变化,和s=x+ys=x+y会依次取遍区间[x+b,x+c][x+b,x+c],每个值恰好对应一个(x,y)(x,y)。

建立数组cntcnt,让cntscnt_s表示有多少对(x,y)(x,y)满足x+y=sx+y=s。对于每个xx,不必枚举所有yy,只要对[x+b,x+c][x+b,x+c]整体增加11:

1
2
cnt[x + b]++;
cnt[x + c + 1]--;

第一次求前缀和以后,cntscnt_s变成和恰好等于ss的数对数量。再求一次前缀和,cntscnt_s就变成和不超过ss的数对数量。

记全部(x,y)(x,y)的数量为totaltotal。对于固定的zz,合法数对数量就是:

total−cntztotal-cnt_z

这道题中的“两次前缀和”有不同职责:第一次还原差分,第二次累计答案。写代码时最好先说清楚数组在每一步表示什么,否则很容易多做或少做一次累加。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int a, b, c, d;
cin >> a >> b >> c >> d;
int lim = max(b + c, d) + 2;
vector<i64> cnt(lim + 1);
for (int x = a; x <= b; x++) { cnt[x + b]++; cnt[x + c + 1]--; }
for (int i = 1; i <= lim; i++) cnt[i] += cnt[i - 1];
for (int i = 1; i <= lim; i++) cnt[i] += cnt[i - 1];

i64 total = cnt[lim], ans = 0;
for (int z = c; z <= d; z++) ans += total - cnt[z];
cout << ans << '\n';
return 0;
}

令V=max⁡(b+c,d)V=\max(b+c,d),数组长度、时间复杂度和空间复杂度均为O(V)O(V)。

总结与常见问题

应该使用哪一种?

  • 数组不再修改,需要大量区间查询:使用前缀和;
  • 每个位置的贡献次数与下标有关:考虑普通前缀和与权值前缀和;
  • 需要查询若干段前缀和的总和:建立二阶前缀和;
  • 静态矩形查询:使用二维前缀和;
  • 先完成大量区间修改,最后统一得到数组:使用差分;
  • 先完成大量矩形修改,最后统一得到网格:使用二维差分;
  • 修改和查询在线交错出现:继续考虑树状数组或线段树。

常见错误

1. 忘记预留第00项

前缀和查询需要访问sl−1s_{l-1}。当l=1l=1时会访问s0s_0,因此数组必须多开一格,并让s0=0s_0=0。

2. 使用 int 保存区间和

即使每个aia_i都能放进 int,nn个数相加、位置权值i⋅aii\cdot a_i以及答案中的乘积仍然可能溢出。涉及累加值时优先检查是否需要 i64。

3. 差分的右端点少加11

闭区间[l,r][l,r]增加kk,结束位置是r+1r+1:

1
2
d[l] += k;
d[r + 1] -= k;

如果把结束位置误写成rr,位置rr本身就不会得到这次修改。

4. 二维容斥的符号写反

无论二维前缀查询还是二维差分修改,都可以先从一维思考:一个方向开始、一个方向结束。不要只背四个位置,先确定每个位置影响的是哪一块区域。

5. 把普通差分当成在线数据结构

差分数组能够快速记录修改,但在重新求前缀和以前,did_i并不是aia_i。修改后立刻查询任意区间时,普通差分通常不够用。

6. 不清楚连续两次前缀和的含义

第一次前缀和可能是在还原差分,第二次才是在统计累计数量。每做一次累加,都应当重新写清楚数组当前保存的内容。

复杂度分析

方法 预处理或还原 单次操作 空间复杂度
一维前缀和 O(n)O(n) 区间查询O(1)O(1) O(n)O(n)
权值或二阶前缀和 O(n)O(n) 区间查询O(1)O(1) O(n)O(n)
二维前缀和 O(nm)O(nm) 矩形查询O(1)O(1) O(nm)O(nm)
一维差分 还原O(n)O(n) 区间修改O(1)O(1) O(n)O(n)
二维差分 还原O(nm)O(nm) 矩形修改O(1)O(1) O(nm)O(nm)