差分是重要的区间专用数据结构，它有与前缀和不同的优势……
差分数据结构与前缀和正好相反，我们举个例子：
假如a[]是输入的数据，那么b[]是a[]的前缀和，这与我们上节课的定义基本一样，那如果b[]是输入数据，那么a[]是b[]的差分。大家可以理解上面那句话的意思了吗？如果不理解，我们通过一个例子：
我们如何构建a[]的差分呢？那么其实很简单，就是当前位置的数字减掉前面位置的数字。比如b[1]=a[1]-a[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]
代码的写法很简单：然后我们来讲讲区间求和。因为差分数组比较特殊，记的是两个数之间的大小关系，所以我们必须转化为简单的方式，转化为普通数组的形式，然后使用普通数组做简单的加法的形式去输出就可以了。比如说以下例子：
我们就应该根据b数组的差分形式重新构建普通数组，构建方法很简单，就是通过从1开始循环到6，然后将前面一位数的值加上当前差分的值，存入c[]即可，比如在c[1]的位置，就加入b[1]的差分结果，在c[2]的位置，就是c[1]+b[2]的结果。遍历之后的结果如下：
然后区间求和的话就循环求和，没有什么难的，代码如下：当然，该程序还可以优化，方法就是将c[]改为c动态变量，那么每一个循环就得到当前的数字，那么我们只要将属于区间内的数字相加即可，不理解的自行理解程序……代码如下：总的来说，程序的时间复杂度为O(n)
最后说说区间最大值，方法与区间求和类似，同样先求出原始数组，然后再找区间中的最大值，而优化方法也是用区间变量的方法，代码如下：时间复杂度依旧为O(n)，速度依旧不快。
已有 2 人购买 本主题需向作者支付 2 鱼币 才能浏览 购买主题
沙发~学习了{:10_257:}
{:5_106:}
若 s 是 a 的前缀和数组，那么 a 是 s 的差分{:10_256:}
zhangjinxuan 发表于 2023-7-23 11:37差分数据结构与前缀和正好相反，我们举个例子：
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 |
| a[] | 0 | 2 | 5 | 17 | 1 | 9 |
| b[] | 0 | 2 | 7 | 24 | 25 | 34 |
假如a[]是输入的数据，那么b[]是a[]的前缀和，这与我们上节课的定义基本一样，那如果b[]是输入数据，那么a[]是b[]的差分。大家可以理解上面那句话的意思了吗？如果不理解，我们通过一个例子：
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 5 |
| a[] | 0 | 2 | 5 | 17 | 1 | 9 | 0 |
| b[] | 0 |
我们如何构建a[]的差分呢？那么其实很简单，就是当前位置的数字减掉前面位置的数字。比如b[1]=a[1]-a[0]，以此类推。构建出来的数组如下：
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 5 |
| a[] | 0 | 2 | 5 | 17 | 1 | 9 | 0 |
| b[] | 0 | 2 | 3 | 12 | -16 | 8 | -9 |
这就创建好了一个差分数组。构建差分数组的代码如下：
#include <iostream>
#include <stdlib.h>
using namespace std;
int a[zxsq-anti-bbcode-1001]={0}, b[zxsq-anti-bbcode-1001];
int n;
int main(void){
cin>>n;
for (int i=1; i<=n; i++){
cin>>a[zxsq-anti-bbcode-i];
}
for (int i=1; i<=n+1; i++){
b[zxsq-anti-bbcode-i]=a[zxsq-anti-bbcode-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[zxsq-anti-bbcode-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]的结果。遍历之后的结果如下：
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| b[] | 0 | 2 | 7 | 12 | -16 | 4 | -9 |
| b[] | 0 | 2 | 9 | 21 | 5 | 9 | 0 |
int sum(int x, int y){
int c[zxsq-anti-bbcode-1000]={0};
for (int i=1; i<=n+1; i++){
c[zxsq-anti-bbcode-i]=c[i-1]+b[zxsq-anti-bbcode-i];
}
int ans=0; //存储总和的变量
for (int i=x; i<=y; i++){
ans+=c[zxsq-anti-bbcode-i];
}
return ans;
}int sum(int x, int y){
int c=0, ans=0;
for (int i=1; i<=n+1; i++){
c+=b[zxsq-anti-bbcode-i];
if (i>=x&&i<=y){
ans+=c;
}
}
return ans;
}最后说说区间最大值，方法与区间求和类似，同样先求出原始数组，然后再找区间中的最大值，而优化方法也是用区间变量的方法，代码如下：
int max1(int x, int y){
int c=0, lmax=0;
for (int i=1; i<=n+1; i++){
c+=b[zxsq-anti-bbcode-i];
if (i>=x&&i<=y){
if (lmax<c){
lmax=c;
}
}
}
return lmax;
}若 s 是 a 的前缀和数组，那么 a 是 s 的差分
看群里消息 sfqxx 发表于 2023-7-23 11:43
看群里消息
什么群，没有啊，rating马上算 zhangjinxuan 发表于 2023-7-23 11:45
什么群，没有啊，rating马上算
就是Evan的atcider用户名错误
输入法不管了 sfqxx 发表于 2023-7-23 11:46
就是Evan的atcider用户名错误
输入法不管了
??? sfqxx 发表于 2023-7-23 11:46
就是Evan的atcider用户名错误
输入法不管了
《Evan》 Ewan-Ahiouy 发表于 2023-7-24 15:04
《Evan》
呃 学习
页:
[1]