欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基本算法——差分

程序员文章站 2023-12-27 08:07:33
...


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

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

一维差分

什么是一维差分?
基本算法——差分
那么差分可以用来干嘛呢?
让我们来看这样一个操作
基本算法——差分
通过差分,我们可以快速对前缀和数组的一个区间的数进去操作

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

输入一个长度为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;
	}
相关标签: 算法学习 算法

上一篇:

下一篇: