差分详解小白专属

大家好，欢迎来到IT知识分享网。

一学就会

一、一维差分

1.一维差分的定义

给定一个数组A它的差分数组B的定义为：$$B[i]=A[i]-A[i-1](2<=i<=n)$$

2.一维差分的操作

一维差分可以让我们在一段区间内加上指定的数，其它位置不变，差分可以帮助我们把“区间操作”变成对差分数组的“单点操作”，降低我们的求解难度。

比如：让我们在a数组的l-r这个区间加上d的话我们就可以先求出a数组的差分数组b，然后在b[l]加上d,然后再在b[r+1]的地方减去d即可。因为差分的前缀和就是原数组（相当于前缀和的逆运算），我们在b[l]的地方加上d通过前缀和求原数组的时候就相当于在下标为l（包括l）之后的数全部加上d，又因为我们只需要在l-r这个区间加上d，所以我们就可以在r+1的地方再减去d即可。

b[l]+=d; b[r+1]-=d; 

3.一维差分相关的例题

#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1e6 + 10; int a[N], b[N]; void add(int l, int r, int d) { b[l] += d; b[r + 1] -= d; } int main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i], add(i, i, a[i]); while (m--) { int l, r, c; cin >> l >> r >> c; add(l, r, c); } for (int i = 1; i <= n; i++) b[i] += b[i - 1]; for (int i = 1; i <= n; i++) cout << b[i] << ' '; return 0; } 

#include <iostream> #include <algorithm> using namespace std; const int N = 1e6 + 10; long long a[N],b[N]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1]; long long sum1=0,sum2=0; for(int i=2;i<=n;i++) { if(b[i]>0) sum1+=b[i]; else sum2+=abs(b[i]); } cout<<min(sum1,sum2)+abs(sum1-sum2)<<endl; cout<<abs(sum1-sum2)+1<<endl; return 0; } 

#include <cstring> #include <iostream> #include <algorithm> #include <set> using namespace std; const int N = 1e6 + 10; int a[N]; int main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, p, h, m; cin >> n >> p >> h >> m; a[1] = h; set<pair<int, int>> se; for (int i = 1, l, r; i <= m; i++) { cin >> l >> r; if (l > r) swap(l, r); if (!se.count({l, r})) { se.insert({l, r}); a[l + 1]--; a[r]++; } } for (int i = 1; i <= n; i++) { a[i] += a[i - 1]; cout << a[i] << endl; } return 0; } 

二、二维差分

1.二维差分的重要操作

可以类比一维差分就是在一个区间内加上一个c，比如我们可以在a数组以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; 

#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1e3 + 10; int a[N][N], b[N][N]; void add(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() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m, q; cin >> n >> m >> q; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; add(i,j,i,j,a[i][j]); } } while(q--) { int x1,x2,y1,y2,c; cin>>x1>>y1>>x2>>y2>>c; add(x1,y1,x2,y2,c); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cout<<a[i][j]<<' '; } cout<<endl; } return 0; }