#创作计划#C++前缀和与差分

AAA逃离森林湖的蔡锡龙批发

2025-08-20 20:39:51

发布于：广东

29阅读

0回复

0点赞

Markdown代码2616字，渲染出实际1934字

前言

前缀和和差分是优化的常见手段。
~~本篇很水~~

前缀和

假设有一个数组 $A$ ,现在要对 $A_l$ 到 $A_r$ 进行求和。

假设 $l=2,r=4$ ,那么求和的操作：
首先新建两个变量： $ans=0$ 用于记录和， $i=l$ 用于求和操作。

$ans=0,i=2$
接下来将 $ans$ 加上 $i$ 指向的值，并将i右移：

$ans=2,i=3$
继续累加 $ans$ 并右移 $i$ ：

$ans=5,i=4$
$i$ 到达 $r$ ，累加 $ans$ 并结束。
最终答案： $ans=8$
可以发现，这里的方法如果用代码实现，时间复杂度很高( $O(r-l+1)$ )，如果题目给到的数据大一点就会爆 $\color{blue}TLE$ 。
这个时候，就可以使用前缀和来优化代码，实现 $O(1)$ 的时间复杂度。
新建一个数组 $S$ ， $S_i$ 表示 $A$ 数组前 $i$ 项的值，即 $S_i=A_1+A_2+\cdots+A_{i-1}+A_i$ 。

$S_1=A_1$
$S_2=A_1+A_2$
$S_3=A_1+A_2+A_3$
$S_4=A_1+A_2+A_3+A_4$
$S_5=A_1+A_2+A_3+A_4+A_5$
$S_6=A_1+A_2+A_3+A_4+A_5+A_6$
依旧是 $l=2,r=4$ 求区间和：
这段区间的区间和是 $A_2+A_3+A_4$ ，刚好等于 $S_4-S_1$ 。

验证答案： $S_4-S_1=9-1=8$ 。答案正确！
也就是说， $l$ 到 $r$ 的区间和为 $S_r-S_{l-1}$ 。
那么如何在程序中快速生成前缀和数组呢？
我们可以注意到， $S_i$ 只比 $S_{i-1}$ 多一个 $A_i$ ，如：
$S_3=A_1+A_2+A_3$
$S_4=\underbrace{A_1+A_2+A_3}_{S_3}+A_4=S_3+A_4$
得出： $S_i=S_{i-1}+A_i$ 。

程序实现

for(int i = 1;i <= n;i++){//输入
	cin >> a[i];
	s[i] = a[i-1]+s[i];
}
cin >> l >> r;//输出
cout << s[r]-s[l-1];

一个小特性：当i=1,程序内s[1]=s[0]+a[1],如果s为全局变量则s[0]等于0,s[1]直接等于a[1]。

差分

有一个数组 $A$ ，现在要将数组中从 $l$ 到 $r$ 区间的数全部加上 $t$ 。
常规暴力实现：假设 $l=2,r=4,t=3$ ，定义一个 $i=l$ 。

将 $i$ 指向的数加上 $t$ ，并将 $i+1$ ：

继续操作：

$i$ 到达 $r$ ，最后一次操作 $i$ 指向的元素加上 $t$ ，循环结束。
结束后的数组 $A$ ：

这个方法的时间复杂度依然是 $O(r-l+1)$ 。
要优化这里的代码，可以使用差分。

差分适用于有多次区间加减的题目，单次加减甚至会负优化( $O(t(r-l+1))$ 到 $O(tn)$ )

增加差分数组 $D$ :

其中 $D_i=A_i-A_{i-1}$ 。
对于每次操作，将 $D_l$ 加上 $t$ ， $D_{r+1}$ 减去 $t$ .
解释：增大 $A_l$ 的值会增大 $D_i(A_i)-A_{i-1}$ 的值，而 $l$ 到 $r$ 区间内的值由于一起加减，差分数组不变。
增大 $A_r$ 的值会减小 $D_{r+1}(A_{r+1}-A_r)$ 的值，所以减去 $t$ 。

此处假设 $D_i$ 只有正数。

最后，给 $D$ 数组做一个前缀和得到原数组 $A$ 。
解释： $D_i=A_i-A_{i-1},A_i=D_i+A_{i-1}$ 。
代码实现：

int n,q,d[12];
cin >> n >> q;//n为数组大小，q为操作次数
int tmp = 0;
for(int i = 1;i <= n;i++){
	int x;cin >> x;
	d[i] = x-tmp;
	tmp=x;
}
while(q--){
	int l,r,t;cin >> l >> r >> t;
	d[l]+=t;
	d[r+1]-=t;
}
tmp=0;
for(int i = 1;i <= n;i++){
	int x = tmp += d[i];
	cout << x << endl;
	tmp=x;
}