专栏文章

算法笔记：前缀和 & 差分

FFreezing_Winter
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minwy2cx
此快照首次捕获于
2025/12/02 09:42
3 个月前
此快照最后确认于
2025/12/02 09:42
3 个月前
查看原文

前缀和

适用范围：区间求和。

一维

例 有一个长度为 nn 的数列 aa，有 qq 次询问，每次询问 ll，rr，要求输出 ∑i=lrai\sum\limits_{i=l}^{r}a_i。
首先考虑暴力，每次询问时：
CPP
int s=0;
for(int i=l;i<=r;i++)s+=a[i];
cout<<s<<'\n';
时间复杂度分析：最劣时，每次都 l=1,r=nl=1,r=n，则时间复杂度为 O(nq)O(nq)。
那么我们怎么优化呢？
我们可以再考虑一个数组 ss 存储 aa 的前缀和，即
si=∑j=1iajs_i=\sum\limits_{j=1}^ia_j
稍作变形便可得出递推式：
si={aii=1si−1+aii>1s_i=\begin{cases}a_i&i=1\\s_{i-1}+a_i&i>1\end{cases}
那么这样有什么用呢？
注意到，∑i=lrai=∑i=1rai−∑i=1l−1ai=sr−sl−1\sum\limits_{i=l}^ra_i=\sum\limits_{i=1}^ra_i-\sum\limits_{i=1}^{l-1}a_i=s_r-s_{l-1}，这样便将 O(n)O(n) 的遍历变成了 O(1)O(1) 的计算，总复杂度直接降为 O(n+q)O(n+q)。
例 参考代码CPP
#include<bits/stdc++.h>
#define int long long
#define N 10000005//本处以n<=1e7举例 
using namespace std;
int a[N],s[N],n,q;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];}
	while(q--){
		int l,r;cin>>l>>r;
		cout<<s[r]-s[l-1]<<'\n';
	}
	return 0;
}

二维

例 有一个 nn 行 mm 列的二维数组 aa，有 qq 次询问，每次询问 x1,y1,x2,y2x_1,y_1,x_2,y_2，求 ∑i=x1x2∑j=y1y2ai,j\sum\limits_{i=x_1}^{x_2}\sum\limits_{j=y_1}^{y_2}a_{i,j}。
本题与上一例极为类似，只是改成了二维。
先考虑暴力，每次 O(nm)O(nm) 的遍历数组，总时间复杂度 O(qmn)O(qmn)。
类似地，设 si,j=∑k=1i∑l=1jak,ls_{i,j}=\sum\limits_{k=1}^i\sum\limits_{l=1}^ja_{k,l}，易得递推式为：
si,j=si−1,j+si,j−1−si−1,j−1+ai,js_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}
可以参考图来理解（绿色部分为黄蓝的重叠处）：
预处理好 ss 后，每次询问时，类似预处理的推导，易得：
∑i=x1x2∑j=y1y2ai,j=sx2,y2−sx1−1,y2−sx2,y1−1+sx1−1,y1−1\sum\limits_{i=x_1}^{x_2}\sum\limits_{j=y_1}^{y_2}a_{i,j}=s_{x_2,y_2}-s_{x_1-1,y_2}-s_{x_2,y_1-1}+s_{x_1-1,y_1-1}
复杂度优化至 O(nm+q)O(nm+q)。

差分

适用范围：区间整体加减。

一维

例 有一个长度为 nn 的数列 aa，有 qq 次操作，每次输入 ll，rr，ww，要求对于每一个 i∈[l,r]i\in[l,r]，都将 aia_i 的值加上 ww，最后输出 aa。
暴力做法为 O(nq)O(nq)，可以使用差分进行优化。
定义差分数组 dd，其中
{aii=1ai−ai−1i>1\begin{cases}a_i&i=1\\a_i-a_{i-1}&i>1\end{cases}
为什么要把差分和前缀和放在一起呢？
我们对差分数组求前缀和，设其为 pp：
pi=∑j=1idj=∑j=1i(aj−aj−1)=aip_i=\sum\limits_{j=1}^id_j=\sum\limits_{j=1}^i(a_j-a_{j-1})=a_i
于是我们得到一个重要的结论：差分数组的前缀和数组为原数组。
类似的，还可以得到：前缀和数组的差分数组为原数组。
所以：前缀和和差分互为逆运算。
回到例题，对于一次操作，设操作后的原数组和差分数组分别为 a′a^\prime 和 b′b^\prime。
分类讨论：
  • 对于任意的 i∈[l+1,r]i\in[l+1,r]，di′=ai′−ai−1′=(ai+w)−(ai−1+w)=did^\prime_i=a^\prime_i-a^\prime_{i-1}=(a_i+w)-(a_{i-1}+w)=d_i。
  • 对于 i=li=l，di′=(ai+w)−ai−1=di+wd^\prime_i=(a_i+w)-a_{i-1}=d_i+w。
  • 对于 i=r+1i=r+1，di′=ai−(ai−1+w)=di−wd^\prime_i=a_i-(a_{i-1}+w)=d_i-w。
综上所述，对于 [l,r][l,r] 的区间整体加 ww 的修改，仅需对差分数组 dd 进行如下修改：
CPP
d[l]+=w;
d[r+1]-=w;
qq 次操作后，只需对 dd 求前缀和并输出即可。
例 参考代码CPP
#include<bits/stdc++.h>
#define int long long
#define N 10000005//本处以n<=1e7举例 
using namespace std;
int a[N],d[N],n,q;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){cin>>a[i];d[i]=a[i]-a[i-1];}
	while(q--){
		int l,r,w;cin>>l>>r>>w;
		d[l]+=w;
		d[r+1]-=w;
	}
	for(int i=1;i<=n;i++){
		a[i]=a[i-1]+d[i];
		cout<<a[i]<<' ';
	}
	return 0;
}
时间复杂度：O(n+q)O(n+q)。

二维

例 有一个 nn 行 mm 列的二维数组 aa，有 qq 次操作，每次操作输入 x1,y1,x2,y2,wx_1,y_1,x_2,y_2,w，对于任意的 i∈[x1,x2]i\in[x_1,x_2] 和 j∈[y1,y2]j\in[y_1,y_2]，将 ai,ja_{i,j} 加上 ww，最后输出 aa。
我们已经知道在一维中，差分和前缀和互为逆运算。类比过来，设差分数组 dd：
di,j=ai,j−ai−1,j−ai,j−1+ai−1,j−1d_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}
对照一维前缀和及差分的迁移，不难想出二维的迁移，这里不写推导过程，作为思考题留给读者，直接给出操作代码：
CPP
d[x_1][y_1]+=w;
d[x_2+1][y_1]-=w;
d[x_1][y_2+1]-=w;
d[x_2+1][y_2+1]+=w;
最后对差分数组求前缀和即可。
时间复杂度：O(mn+q)O(mn+q)。

课后作业

算法笔记：前缀和 & 差分 课后作业。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...