您现在的位置是：首页 >其他 >领略算法真谛：差分网站首页其他

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！

我的博客：yuanManGan

我的专栏：C++入门小馆 C言雅韵集 数据结构漫游记  闲言碎语小记坊 题山采玉

目录

差分

⼀维差分

题目理解：

思路讲解：

代码实现：

⼆维差分

题目理解：

思路讲解：

代码展示：

练习题：

答案：

---

差分

差分主要是用于对一个区间整体加或者减去同一个数这类问题，这里还是以一道题为例子展开吧

⼀维差分

题目理解：

给了一个长度为n的数组，要求对数组 l 到 r 区间进行加上 k 的处理进行m次，然后输出数组的所有元素。

思路讲解：

暴力解法：

要求对那个区间进行操作我们就一次for循环加上k就行了，但时间复杂度为m*n(1e5 * 1e5)显然会超时，这时我们就引出了差分数组

差分：

我们依旧像前缀和一样，创建一个差分数组，这里存储的不再是前缀和，而是这一位元素减去上一位元素的值

这就是一个差分数组，但我们要解决题目，这个差分数组有什么用呢？别急，我们先对原数组一个区间加上一个数，发现差分数组只改变了两个数，时间复杂度就从O(n)变成了O(1)了。

我们如果要在x~y区间加上k，就等价于a[x] += k , a[ y  + 1] -= k.只需要改变这两个数就可以解决问题了。

心急的朋友这时又要问了，那我怎么还原原数组呢，我们仅需要对差分数组求前缀和就解决问题了，是不是很奇妙呢，所以说差分与前缀和互为逆运算。

代码实现：

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
//差分数组
LL f[N];
int main()
{
	cin >> n >> m;
	//预处理
	for (int i = 1; i <= n; i++)
	{
		LL x; cin >> x;
		f[i] += x;
		f[i + 1] -= x;
	}
	//进行m次操作
	while (m--)
	{
		int l, r, k; cin >> l >> r >> k;
		f[l] += k, f[r + 1] -= k;
	}
	//对差分数组求前缀和还原
	for (int i = 1; i <= n; i++)
	{
		f[i] += f[i - 1];
		cout << f[i] << " ";
	}

	return 0;
}

⼆维差分

题目理解：

给了个二维数组，要求对以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k，进行q次操作，最后输出数组

思路讲解：

暴力解法：

叫你加你就加，老老实实最后换来时间复杂度：O(n * m * q) = 1e4 * 1e4 * 1e5。时间复杂度都上天了。

二维差分：

差分数组的初始化先别忙着讲，先解决对以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k，这个问题，然后x1 = x2，y1 = y2, k = x，不就解决了差分数组初始化的问题了吗？

这是原数组，我们像实现如图的功能 。

我们从一维数组了解到，对差分数组求前缀和能得到原始数组，那我们不妨假设一个差分数组对任意位置加上一个k试试

然后我们对这个数组求前缀和，发现以x1，y1为左上角的矩阵的前缀和都受到了影响，都加上了k。

但我们只需但我们只需要对 以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k，我们再把边上的减去就成了：

发现就差一点就能完成任务了，最后将x2 + 1， y2 + 1位置加上k就大功告成了！

代码展示：

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e4 + 10;

//差分数组
LL f[N][N];

int n, m, q;
//添加k操作
void insert(LL x1, LL y1, LL x2, LL y2, LL k)
{
	f[x1][y1] += k; f[x2 + 1][y2 + 1] += k;
	f[x1][y2 + 1] -= k; f[x2 + 1][y1] -= k;
}
int main()
{
	cin >> n >> m >> q;
	//预处理差分数组
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			LL x; cin >> x;
			insert(i, j, i, j, x);
		}
	}
	//进行q次操作
	while (q--)
	{
		int x1, y1, x2, y2, k;
		cin >> x1 >> y1 >> x2 >> y2 >> k;
		insert(x1, y1, x2, y2, k);
	}
	//前缀和差分数组还原原数组
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
			cout << f[i][j] << " ";
		}
		cout << endl;
	}
}

练习题：

一维差分：

海底高铁

二维差分：

地毯 

答案：

海底高铁：

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
LL f[N];
int main()
{
	cin >> n >> m;
	int x; cin >> x;
	for (int i = 2; i <= m; i++)
	{
		int y; cin >> y;
		if (x > y) f[x]--, f[y]++;
		else f[y]--, f[x]++;
		x = y;
	}
	//还原原数组
	for (int i = 1; i <= n; i++) f[i] += f[i - 1];
	LL ret = 0;
	for (int i = 1; i < n; i++)
	{
		int a, b, c; cin >> a >> b >> c;
		ret += min(a * f[i], c + b * f[i]);
	}
	cout << ret << endl;
	return 0;
}

地毯：

#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int f[N][N];
int main()
{
	cin >> n >> m;
	while (m--)
	{
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		f[x1][y1]++; f[x2 + 1][y1]--; 
		f[x1][y2 + 1]--; f[x2 + 1][y2 + 1]++;
	}
	//还原
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
			cout << f[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}