前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第九讲：差分【例/习题】
本篇博客所包含习题有：
👊差分
👊差分矩阵
有关差分的内容细致讲解见博文：差分
有关差分的模板见博文：差分算法模板
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
差分
题目要求
题目描述：
输入格式：
输出格式：
共一行，包含 n 个整数，表示最终序列。
数据范围：
输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2
思路分析
一维差分的模板题，对于差分你可以理解成为前缀和的逆运算，差分数组的构造方法为：
s数组是差分数组,a数组是原数组 s[0] = 0, a[0] = 0; s[1] = a[1] - a[0]; s[2] = a[2] - a[1]; ... s[n] = a[n] - a[n - 1];
令 a 数组在 [ l , r ] 的区间内加上一个数 c可以用差分的思维：
s[l] += c; s[r + 1] -= c;
然后对差分数组做一遍前缀和即可。
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int a[N], s[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 ++ ) s[i] = a[i] - a[i - 1]; while (m -- ) { int l, r, c; scanf("%d%d%d", &l, &r, &c); s[l] += c, s[r + 1] -= c; } for (int i = 1; i <= n; i ++ ) { s[i] += s[i - 1]; printf("%d ", s[i]); } return 0; }
差分矩阵
题目要求
题目描述：
输入格式：
输出格式：
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。
数据范围：
输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
输出样例：
2 3 4 1
4 3 4 1
2 2 2 2
思路分析
对于二维差分数组，你可以这么去理解：如果前缀和的二维矩阵上的某一点是影响从矩阵左上角到该点内的数，那么差分数组矩阵就是影响从这一点到矩阵右下角，往 a 数组（二维） ( x 1 , y 1 )【左上角】和 ( x 2 , y 2 ) 【右下角】的矩阵内加上一个数 c可用差分：
s[x1][y1] += c; s[x2 + 1][y1] -= c; s[x1][y2 + 1] -= c; s[x2 + 1][y2 + 1] += c;
然后再计算一遍前缀和数组，即可得到结果，注意我们的前缀和模板应该是：
s[i, j] = s[i, j - 1] + s[i - 1, j] - s[i - 1, j - 1] + a[i, j];
但此时的 s [ i , j ]其实就是一个值，即也为 a [ i , j ]，故把差分数组变为前缀和数组为：
s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int a[N][N], s[N][N]; void insert(int x1, int y1, int x2, int y2, int c) { s[x1][y1] += c; s[x2 + 1][y1] -= c; s[x1][y2 + 1] -= c; s[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, y1, x2, 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 ++ ) s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1]; for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) printf("%d ", s[i][j]); puts(""); } return 0; }
