差分算法（仅总代码收费）

bangbang-ande · 发表于 2023-7-23 10:32:39

差分是重要的区间专用数据结构，它有与前缀和不同的优势……
差分数据结构与前缀和正好相反，我们举个例子：

数组	1	2	3	4	5
a[]	2	5	17	1	9
b[]	2	7	24	25	34

假如a[]是输入的数据，那么b[]是a[]的前缀和，这与我们上节课的定义基本一样，那如果b[]是输入数据，那么a[]是b[]的差分。大家可以理解上面那句话的意思了吗？如果不理解，我们通过一个例子：

数组	1	2	3	4	5	5
a[]	2	5	17	1	9	0
b[]

我们如何构建a[]的差分呢？那么其实很简单，就是当前位置的数字减掉前面位置的数字。比如b[1]=a[1]-a[0]，以此类推。构建出来的数组如下：

数组	1	2	3	4	5	5
a[]	2	5	17	1	9	0
b[]	2	3	12	-16	8	-9

这就创建好了一个差分数组。构建差分数组的代码如下：

#include <iostream>
#include <stdlib.h>
using namespace std;
int a[1001]={0}, b[1001];
int n;
int main(void){
cin>>n;
for (int i=1; i<=n; i++){
cin>>a[i];
}
for (int i=1; i<=n+1; i++){
b[i]=a[i]-a[i-1];
}
return 0;
}

复制代码

然后就是我们上节课的三件套：区间添加数，区间求和，区间最大值。而差分最优秀的地方就在于区间添加数。其原理也十分巧妙。

假如我们以上面例子，在[2,4]的中间区间添加数，那么做法很简单，在2的位置+4，在5的位置-4，此时有的同学肯定不理解为什么。

我们画一个图出来：
[attach]174013[/attach]
我们需要知道，在2位置+4是对后面的所有数都+4的，因为差分仅保存两数之间距离，当它根据两数间距离恢复成前缀和数组时，就会知道它对每一个数都+4。那在5位置-4也是同理的。那么在5之后的位置既+4，又-4，就相当于抵消掉了，就只剩下2~4的区间添加了4，我们所需要的任务也完成了，正如下图一样：
[attach]174014[/attach]
代码的写法很简单：

int add(int x, int y, int p){
b[x]+=p;
b[y+1]-=p;
}

复制代码

然后我们来讲讲区间求和。因为差分数组比较特殊，记的是两个数之间的大小关系，所以我们必须转化为简单的方式，转化为普通数组的形式，然后使用普通数组做简单的加法的形式去输出就可以了。比如说以下例子：

数组	0	1	2	3	4	5	6
b[]	0	2	7	12	-16	4	-9

我们就应该根据b数组的差分形式重新构建普通数组，构建方法很简单，就是通过从1开始循环到6，然后将前面一位数的值加上当前差分的值，存入c[]即可，比如在c[1]的位置，就加入b[1]的差分结果，在c[2]的位置，就是c[1]+b[2]的结果。遍历之后的结果如下：

数组	1	2	3	4	5	6
b[]	2	7	12	-16	4	-9
b[]	2	9	21	5	9	0

然后区间求和的话就循环求和，没有什么难的，代码如下：

int sum(int x, int y){
int c[1000]={0};
for (int i=1; i<=n+1; i++){
c[i]=c[i-1]+b[i];
}
int ans=0; //存储总和的变量
for (int i=x; i<=y; i++){
ans+=c[i];
}
return ans;
}

复制代码

当然，该程序还可以优化，方法就是将c[]改为c动态变量，那么每一个循环就得到当前的数字，那么我们只要将属于区间内的数字相加即可，不理解的自行理解程序……代码如下：

int sum(int x, int y){
int c=0, ans=0;
for (int i=1; i<=n+1; i++){
c+=b[i];
if (i>=x&&i<=y){
ans+=c;
}
}
return ans;
}

复制代码

总的来说，程序的时间复杂度为O(n)
最后说说区间最大值，方法与区间求和类似，同样先求出原始数组，然后再找区间中的最大值，而优化方法也是用区间变量的方法，代码如下：

int max1(int x, int y){
int c=0, lmax=0;
for (int i=1; i<=n+1; i++){
c+=b[i];
if (i>=x&&i<=y){
if (lmax<c){
lmax=c;
}
}
}
return lmax;
}

复制代码

时间复杂度依旧为O(n)，速度依旧不快。

购买主题 已有 2 人购买 本主题需向作者支付 2 鱼币 才能浏览

Ewan-Ahiouy · 发表于 2023-7-23 10:33:41

沙发~学习了

歌者文明清理员 · 发表于 2023-7-23 11:07:47

zhangjinxuan · 发表于 2023-7-23 11:37:44

若 s 是 a 的前缀和数组，那么 a 是 s 的差分

sfqxx · 发表于 2023-7-23 11:43:59

zhangjinxuan 发表于 2023-7-23 11:37
若 s 是 a 的前缀和数组，那么 a 是 s 的差分

看群里消息

zhangjinxuan · 发表于 2023-7-23 11:45:35

sfqxx 发表于 2023-7-23 11:43
看群里消息

什么群，没有啊，rating马上算

sfqxx · 发表于 2023-7-23 11:46:56

zhangjinxuan 发表于 2023-7-23 11:45
什么群，没有啊，rating马上算

就是Evan的atcider用户名错误

输入法不管了

zhangjinxuan · 发表于 2023-7-23 11:52:58

sfqxx 发表于 2023-7-23 11:46
就是Evan的atcider用户名错误

输入法不管了

???

Ewan-Ahiouy · 发表于 2023-7-24 15:04:01

sfqxx 发表于 2023-7-23 11:46
就是Evan的atcider用户名错误

输入法不管了

《Evan》

sfqxx · 发表于 2023-7-24 15:11:04

Ewan-Ahiouy 发表于 2023-7-24 15:04
《Evan》

呃

Fxcjcj · 发表于 2023-7-24 15:26:00

学习

账号		自动登录	找回密码
密码			立即注册

[技术交流] 差分算法（仅总代码收费）