一、差分的特点和原理
对于一个数组a[]，差分数组diff[]的定义是:
对差分数组做前缀和可以还原为原数组:
利用差分数组可以实现快速的区间修改，下面是将区间[l, r]都加上x的方法:
diff[l] += x; diff[r + 1] -= x;
在修改完成后，需要做前缀和恢复为原数组，所以上面这段代码的含义是:
diff[l]+=x表示将区间[l, n]都加上x但是[r+1,n]我们并不想加x，所以再将[r+1,n]减去x即可。
但是注意，差分数组不能实现“边修改边查询(区间和)，只能实现"多次修改完成后多次查询"。如果要实现“边修改边查询”需要使用树状数组、线段树等数据结构。
二、差分的实现
直接循环O(n)实现即可，注意这里建议使得a[0] = 0，下标从1开始。
for(int i = 1; i <= n; ++i) diff[i] = a[i] - a[i - 1];
将区间[l, r]都加上x：
diff[l] += x; diff[r + 1] -= x;
三、区间更新
问题描述
给定一个长度为 n 的数组 a[1], a[2], ..., a[n]。同时给定 m 个操作，每个操作包含三个整数数据 x, y, z。每个操作的意义是给数组中下标为 x 到下标为 y 之间（包括 x 和 y）的元素的值都加上 z。
输入格式
输入包含多组数据，数据组数不大于 5。
每组数据的第一行有两个整数 n, m（0 < n, m < 100），分别表示数组的长度和操作的数量。
第二行有 n 个整数，分别代表 a[1], a[2], ..., a[n]（0 ≤ a[i] < 10）的初始值。
接下来 m 行，每行包含三个整数 x, y, z（1 ≤ x ≤ y ≤ n, 0 < z < 10），表示一个操作。
输出格式
对于每组数据，输出一行，包含这个序列的所有元素的值，并且每个值之间应该以空格隔开。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 9; vector<int>a(N), b(N); void solve(int n, int m) { for (int i = 1; i <= n; i++)cin >> a[i]; for (int i = 1; i <= n; i++)b[i] = a[i] - a[i - 1];// 初始化差分数组 while (m--) { int l, r, x; cin >> l >> r >> x; b[l] += x; b[r + 1] -= x; // 区间[l,r] [l]+x [r+1]-x } for (int i = 1; i <= n; i++)a[i] = a[i - 1] + b[i]; for (int i = 1; i <= n; i++)cout << a[i] << " \n"[i == n];必须是双引号，\之前可以写空格或者逗号 } int main() { int n, m; // 输入 n, 表示 a[n] 的元素个数 // 输入 m, 表示 m 行 while (cin >> n >> m)solve(n, m); return 0; }
四、肖恩的投球游戏
问题描述
小羊肖恩最近喜欢上了投球游戏，具体来说，在他面前摆放了n个球筐，第i个框最开始有ai个球。
接下来小羊会进行q次操作，每次操作会给出三个整数 l, r,c，会将第l个框到第r个框，都投入c个球。请你输出操作完成之后每个框各有多少个球?
输入格式
第一行输入两个整数n和q，表示球筐个数和操作次数。
第二行输入n个整数，表示每个球筐最开始的球数。
接下来q行，每次输入三个整数l, r, c。
数据范围保证:1 ≤n, q ≤1e3，1 ≤l <r ≤n，1 ≤ai,c≤1e5。
输出格式
输出一行n个整数，表示每个框最终的球的个数，以空格分开。
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 9; vector<int> a(N), b(N); // a[N] 是存储球框最开始的球数 // b[N] 是差分数组 int main() { int n, q; cin >> n >> q; // n, 表示球框个数, q, 表示操作次数 for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i <= n; i++) { b[i] = a[i] - a[i - 1]; // 差分 } while (q--) { int l, r, c; cin >> l >> r >> c; b[l] += c; b[r + 1] -= c; } for (int i = 1; i <= n; i++) { a[i] = a[i - 1] + b[i]; } for (int i = 1; i <= n; i++)cout << a[i] << " \n"[i == n]; return 0; }
五、肖恩的投球游戏加强版
问题描述
小羊肖恩最近喜欢上了投球游戏，但他已经不满足只有一行球筐的玩法了。
具体来说，在他面前摆放了n x m个球筐，这些球筐形成了一个n x m的矩阵，整数a(i,j)表示第i行第j列的球筐最开始的球的个数。
接下来小羊会进行q次操作，每次操作会给出五个整数
x1,x2,y1,y2,c他会将以(x1, y1)为左上角，(x2, y2)为右下角的球筐矩阵都投入c个球。请你输出操作完成之后每个框各有多少个球?
输入格式
第一行输入三个整数n, m, q，表示球筐矩阵的大小和操作次数。接下来n行，每行包含m个整数，表示球筐矩阵。
接下来q行，每次输入五个整数x1,x2,y1,y2,c。
数据范围保证:1≤q≤ 1e5，1≤n, m ≤ 1e3，1 ≤x1≤x2≤n，1≤y1≤y2≤m， 1 ≤a(i,j),c≤105。
#include<bits/stdc++.h> using namespace std; const int N = 1e3 + 9; using LL = long long; int main() { int n, m, q; cin >> n >> m >> q; // 输入 n行 m列, 输入 q 表示操作次数 vector<vector<LL>>a(n + 2, vector<LL>(m + 2)), b(n + 2, vector<LL>(m + 2)); // 创建一个数组来接收球, 创建一个差分数组 for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j]; while (q--) { int x1, x2, y1, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; b[x1][y1] += c; b[x1][y2 + 1] -= c; b[x2 + 1][y1] -= c; b[x2 + 1][y2 + 1] += c;// 减了两次要加回去一次 } for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)b[i + 1][j] += b[i][j]; for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)b[i][j + 1] += b[i][j]; // 右上两个点要加回去 for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)a[i][j] += b[i][j]; for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)std::cout << a[i][j] << " \n"[j == m]; return 0; }
今天就先到这了！！！
看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。
