领略算法真谛：差分

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的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;
}