开发者社区> 辰Chen> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

差分

简介: 复习acwing算法基础课的内容,本篇为讲解基础算法:差分,关于时间复杂度
+关注继续查看

文章目录

前言

一、差分,差分数组

1.什么是差分,差分数组

2.如何得到差分数组

3.差分数组的作用

二、一维差分与二维差分

1.一维差分

一维差分模板

例一:AcWing797. 差分

AC代码

2.二维差分

二维差分模板

例二:AcWing798. 差分矩阵

AC代码

三、时间复杂度


前言

复习acwing算法基础课的内容,本篇为讲解基础算法:差分,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上.


一、差分,差分数组

1.什么是差分,差分数组

差分可以看做前缀和的逆运算,同前缀和一样,差分数组从1号位置点开始,假设我们有一个原数组a:a[1], a[2], a[3] … a[i],我们需要构造出一个数组b:b[1], b[2], b[3] … b[i],使得 a[i] = b[1] + b[2] + b[3] + … + b[i],即数组a是数组b的前缀和数组,即每一个a[i] 都可以对b数组从 1 ~ i 求前缀和得到

2.如何得到差分数组

这一步的操作有点像高中数列中的叠加法的逆运算:

image.png

对于a[0],把数组a全局定义即可。


3.差分数组的作用

对于这么一种情况,我们可以利用差分数组来快速解题:将数组a的[l, r]这一区间内加上一个常数c,最暴力的做法:利用for循环遍历a数组,并在[l, r]区间内加上c,如果有m次操作,这样下来的时间复杂度为O(n * m),差分则是对这一步骤的优化。


难点:我们要明确数组a是数组b的前缀和数组,即数组b的[1 ~ i]个元素的和等于 a[i],故如果我们对b数组的某一项加上c,比如在b[2]加上一个常数c,数组b中的剩余元素不进行处理,这一操作的结果是对于数组b而言只是把b[2]变成b[2] + c,而反应到数组a上,对数组b求前缀和得到数组a,所以当b[2]发生改变后a数组从a[2] ~ a[n]都加上了常数c,如果还没有理解的话,这里给出一个例子帮助理解:


image.png

同理,我们如果让 b[2] 减去一个常数c的话,那么对于b的前缀和数组a而言,从a[2]开始到a[n]全部都会减去一个数c,那么我们利用差分数组b的这一性质,就可以通过改变数组b的两个元素的值,就可以实现将数组a的 [l, r] 这一区间加上或者减去一个数,例:我们欲将数组a的[2~7]这一区间内加上一个数6,具体实现为:

b[2] += 6, b[8] -= 6;

即从a[2]开始以后的每一项都加上一个6,从a[8]开始以后的每一项都减去一个6,那么对于a[8]和之后的所有元素,同时加上减去一个相同的数,相当于未发生改变,而对于a[2] ~ a[7]这一段区间,加上了一个6.


二、一维差分与二维差分

1.一维差分

在一、差分,差分数组中已经介绍了一维差分,这里不做过多赘述,直接上模板和例题


一维差分模板

我们要将一个数列a的[l, r]范围内加上(或减去)一个数c,可对a的差分数组b进行如下操作

b[l] += c, b[r + 1] -= c;

例一:AcWing797. 差分

本题链接:AcWing797. 差分

本博客给出本习题截图:

image.png

AC代码

#include <cstdio>

using namespace std;

const int N = 100010;

int a[N], b[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
    for (int i = 1; i <= n; i ++ ) b[i] = a[i] - a[i - 1];       //b为a的差分数组
    
    while (m -- )
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        b[l] += c, b[r + 1] -= c;                               //差分模板
    }
    
    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];            //计算前缀和
    //此时的b数组就是前缀和数组了,即要输出的变化后的数组a
    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);
    
    return 0;
}

2.二维差分

二维差分的分析思路其实和二维前缀和类似,如图:

image.png

二维差分模板

现我们想让如图中黄色部分加上一个常数c,进行如下操作

b[x1][y1] += c;          //从(x1,y1)坐标往右下角走,所有的数都加一个c
b[x1][y2 + 1] -= c;      //从(x1,y2 + 1)坐标往右下角走,所有数都减一个c
b[x2 + 1][y1] -= c;      //从(x2 + 1,y1)坐标往右下角走,所有数都减去一个c
b[x2 + 1][y2 + 1] += c;  //从(x2 + 1,y2 + 1)坐标往右下角走,所有数都加上一个c(因为被多减去一个c)

例二:AcWing798. 差分矩阵

原题链接:AcWing798. 差分矩阵

本博客给出题目截图:

image.png

image.png

AC代码

#include <cstdio>

using namespace std;

const int N = 1010;

int a[N][N], b[N][N];

void insert(int x1,int y1,int x2,int y2,int c)         //求差分矩阵
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);
            
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);
        
    while (q -- )
    {
        int x1, x2, y1, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];  //求前缀和,即操作后的a
            
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
            printf("%d ", b[i][j]);
        puts("");
    }
    
    return 0;
}

三、时间复杂度

关于差分的时间复杂度以及证明,后续会给出详细的说明以及证明过程,目前先鸽了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
别搞混了!
HTTP 的 Keep-Alive,是由应用层(用户态) 实现的,称为 HTTP 长连接; TCP 的 Keepalive,是由 TCP 层(内核态) 实现的,称为 TCP 保活机制
34 0
tf变换(1)
TF库的目的是实现系统中任一个点在所有坐标系之间的坐标变换,也就是说,只要给定一个坐标系下的一个点的坐标,就能获得这个点在其他坐标系的坐标.  使用tf功能包,a. 监听tf变换: 接收并缓存系统中发布的所有参考系变换,并从中查询所需要的参考系变换。
1405 0
最大差值(贪心)
题目描述 有一个长为n的数组A,求满足0≤a≤b ans) { //比较最大差值 ans = A[i]-min; } } retu...
696 0
二分检索
  现在理论的还是少说些,例子更能理解吧,来个例子用二分检索算法设计与分析,下面算法函数过程bin_search有n+2个输入:a,n 和 x,一个输出j。只要待检索的元素存在,while循环就继续下去。
633 0
无人言说【два】
我梦见有眼睛睁开了,窗帘挡住了清爽的早晨。 早晨和你都是蓝色的。 你撩开发梢,一枚轻吻印在了我的脸颊,寒冷逐渐退怯。 我以为醒了,告诉你梦里繁星密布。 在另一个梦里,我的尸体徒步跋涉,去和你告别。
495 0
备注
 1.绝对的大牛,受益很多,特别是《数据结构》部分 http://www.cnblogs.com/JCSU/articles/1305678.html                         在VMware Workstation的Ubuntu下安装和配置Hadoop与Ganglia: http://www.
725 0
二分覆盖
#include #include #include #include #include using namespace std; //this program's file name is coin.
701 0
+关注
辰Chen
CSDN人工智能领域优质创作者,华为云&middot;云享专家,CCF-TYUT President-designate
719
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载