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

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[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]的结果。遍历之后的结果如下：

数组	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[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;

}

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

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;

}

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

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;

}

时间复杂度依旧为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

学习

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

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