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