文章目录
前言
一、差分，差分数组
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.如何得到差分数组
这一步的操作有点像高中数列中的叠加法的逆运算：
对于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，如果还没有理解的话，这里给出一个例子帮助理解：
同理，我们如果让 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. 差分
本博客给出本习题截图：
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.二维差分
二维差分的分析思路其实和二维前缀和类似，如图：
二维差分模板
现我们想让如图中黄色部分加上一个常数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. 差分矩阵
本博客给出题目截图：
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; }
三、时间复杂度
关于差分的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
