当前位置:首页 > 技术学院 > 技术前线
[导读]基本算法——差分

目标,掌握差分的概念、和解题的思路

差分就是前缀和的逆过程!!!

一维差分

什么是一维差分?


那么差分可以用来干嘛呢?

让我们来看这样一个操作


通过差分,我们可以快速对前缀和数组的一个区间的数进去操作

再思考,如何构建差分呢??需要构建嘛

题目

输入一个长度为n的整数序列。

接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。

请你输出进行完所有操作后的序列。

题解


这里需要注意:我们构造差分的方法是insert(i,i,s[i]);

通过插入的方法我们自然而然的就可以得到差分了


模板

a是s的差分,想要对s[l,r]中的一系列数操作

a[l] += val;

a[r+1] -= val;

二维差分

和前缀和类似,我们也有二位差分,就是对一个前缀和的矩阵中一系列数操作

题目

输入一个n行m列的整数矩阵,再输入q个操作,每个操作包含五个整数x1, y1, x2, y2, c,其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上c。

请你将进行完所有操作后的矩阵输出。

思路还是一样,用差分来做

题解



注意:这里输出的时候用的是BufferWrite()

当要输出大量数据的时候可以使用bw,可以有效节省时间

还有要记得关闭资源哦!!!

模板

public static void insert(int x1, int y1, int x2, int y2, int val){

a[x1][y1] += val;

a[x1][y2+1] -= val;

a[x2+1][y1] -= val;

a[x2+1][y2+1] += val;

}

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

Oct. 20, 2022 ---- 全球市场研究机构TrendForce集邦咨询公告「2023年集邦拓墣科技产业大预测」,精彩内容节录如下:

关键字: TrendForce集邦咨询 拓墣科技

Oct. 19, 2022 ---- 根据TrendForce集邦咨询调查显示,2022年第三季全球电视出货量达5,139万台,季增12.4%,年减2.1%,是自2014年以来同季出货最低纪录。由于全球仍持续垄罩在高通胀...

关键字: TrendForce集邦咨询 OLED

实际上函数指针本质也是一个指针,只不过这个指针指向的不是内存中的一段数据而是内存中的一段代码

关键字: 指针 数据 代码

为增进大家对控制器的认识,本文将对影响控制器可靠性的因素以及控制器的常见故障和维修方法予以介绍。

关键字: 控制器 指数 集成电路

为增进大家对控制器的认识,本文将对温度控制器的分类以及温度控制器的功能予以介绍。

关键字: 温度控制器 指数 控制器

为增进大家对控制器的认识,本文将对控制器结构类异常以及常见的几种电机控制器予以介绍。

关键字: 控制器 指数 电机

为增进大家对变频器的认识,本文将对变频器的15大选择技巧予以介绍。

关键字: 变频器 指数 电机

为增进大家对变频器的认识,本文将对变频器的节能功能,以及变频器欠电压故障的解决方法予以介绍。

关键字: 变频器 指数 UPS

为增进大家对变频器的认识,本文将对变频器,以及我们在购买变频器的时候需要注意到的一些事项予以介绍。

关键字: 变频器 指数 逆变电路

Oct. 18, 2022 ---- 根据TrendForce集邦咨询最新调查表示,疫情后紧张的物料情况已于今年下半年改善,短料的供货交期显著恢复。然而在物料供给无虞,需求可被满足的情况下,2023年的服务器整机出货量年...

关键字: TrendForce集邦咨询 服务器

技术前线

2090 篇文章

关注

发布文章

编辑精选

技术子站

关闭