当前位置：首页 > news >正文

基础算法——差分

news 来源：原创 2025/5/9 7:19:53

原理与特点

先回顾一下前缀和算法。
| arr | 1 | 3 | 7 | 5 | 6 |
| ---------- | ------ | ------ | ------ | ------ | ------ |
| prefix 值 | 1+0=1 | 1+3=4 | 1+3+7=11 | 1+3+7+5=16 | 1+3+7+5+6=22 |
前缀和的特点是前面的相加prefix(i)=sum(i-1)+arr(i)。
那么差分数组diff就如下面的形式
| arr | 1 | 3 | 7 | 5 | 6 |
| ---------- | ------ | ------ | ------ | ------ | ------ |
| diff 值 | 1-0=1 | 3-1=2 | 7-3=4 | 5-7=-2 | 6-5=-1 |
我们把差分数组进行前缀和计算可以得到原来的arr数组，因此可以理解为前缀和的逆运算
这有什么用？
请看以下例子
我想的得到arr数组(下标从1开始放数字),2->4的数字加5,即[2,4]+5,然后[1,3]+2,[0,2]-3,之后的数组是什么样的？
如果方法为每访问一次就计算一次，那么有n个数字访问m次，那么时间复杂度为O(mn)
利用上面差分和前缀和的性质，
[L,R] + v = d[L]+v,d[R+1]-v,每访问一次就对差分数组进行一次这样的操作，然后把访问之后的最终数组，进行前缀和处理就可以得到答案。

原理分析

[2,4]+5,[1,3]+2,[0,2]-3,每一个过程可看作以下步骤
| diff 值 | 1-0=1 | 3-1=2 | 7-3=4 | 5-7=-2 | 6-5=1|
|[2,4]+5 | 1 | 2+5=7 | 4 | -2 | 1-5=-4 |
| 前缀和还原 | 1 | 8 | 12 | 5 | 6 |

规律总结

可以发现，我们先对diff数组==[L,R] + v = d[L]+v,d[R+1]-v==处理，然后进行前缀和处理还原，就是在[l,r]区间进行+v的操作，那么我们在遇到这样的问题时，直接先把原数组的差分数组弄出来：diff[i] = arr[i] - arr[i - 1],然后进行处理，处理次数依情况而定，最后再前缀和还原，这样时间复杂度就是O(m+n),线性，大大优化。

例题1

问题描述

给定一个长度为 n的数组 a[1],a[2],…,a[n]a[1],a[2],…,a[n]。同时给定 m 个操作，每个操作有三个整形数据 x,y,z。每个操作的意义就是给数组中下标为 x 与下标为 y 之间（包括 x,yx,）的元素的值加上 z。

输入格式

输入有多组数据，数据组数不大于 55。每一组数据第一行有两个整数 n,m(0<n,m<105)。第二行有 n 个整数，分别代表 a[1],a[2],…,ana[1],a[2],…,an 的初始值。接下来就 m 行，每一行有 3 个整数 x,y,z(0<x≤y≤n,0<z<10)x,y,z(0<x≤y≤n,0<z<10)。

输出格式

在一行内输出这个序列的所有元素的值，并且每个值之间应该以空格隔开。

输入样例

10 5
0 0 0 0 0 0 0 0 0 0
1 5 1
2 6 1
3 7 1
4 9 1
5 10 1
1 1
1
1 1 2

输出样例

1 2 3 4 5 4 3 2 2 1
3

问题分析：
如果访问一次处理一次，时间复杂度会达到O(mn),如果我们用上述的思想，复杂度就是O(m + n)
核心代码如下

例题二

题目描述
小明拥有
N
N 个彩灯，第
i
i 个彩灯的初始亮度为
a
i
a
i

。

小明将进行
Q
Q 次操作，每次操作可选择一段区间，并使区间内彩灯的亮度
+
x
+x（
x
x 可能为负数）。

求
Q
Q 次操作后每个彩灯的亮度（若彩灯亮度为负数则输出
0
0）。

输入描述
第一行包含两个正整数
N
，
Q
N，Q，分别表示彩灯的数量和操作的次数。

第二行包含
N
N 个整数，表示彩灯的初始亮度。

接下来
Q
Q 行每行包含一个操作，格式如下：

l r x，表示将区间
l
∼
r
l∼r 的彩灯的亮度
+
x
+x。

1
≤
N
,
Q
≤
5
×
1
0
5
1≤N,Q≤5×10
5
，
0
≤
a
i
≤
1
0
9
0≤a
i

≤10
9
，
1
≤
l
≤
r
≤
N
1≤l≤r≤N，
−
1
0
9
≤
x
≤
1
0
9
−10
9
≤x≤10
9

输出描述
输出共
1
1 行，包含
N
N 个整数，表示每个彩灯的亮度。

输入输出样例
示例 1
输入

5 3
2 2 2 1 5
1 3 3
4 5 5
1 1 -100
copy
输出

0 5 5 6 10
copy
运行限制
最大运行时间：1s
最大运行内存: 128M

题目链接

主体代码与上述一直，不过要更改数据范围，还有输出条件。