前缀和和差分是互相正逆运用的产物。2023-08-13 00:30:28
1.一维前缀和
令 a 数组 b[i] 代表 b[1]+b[2]+b[3]+…+b[i]
Q：问 b[l] 到 b[r] 的和
A: O（n），核心步骤：
在读取b每步都记录 a[i] = b[i]+a[i-1]，最后只要输出 a[r+1] - a[l]
以下为代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 int a[100005],b[100005],n,m,l,r; 5 int main() 6 { 7 cin>>n>>m; 8 for(int i = 1 ; i <= n ; i++) 9 { 10 cin>>b[i]; 11 a[i]=a[i-1]+b[i]; 12 } 13 while(m--) 14 { 15 cin>>l>>r; 16 cout<<a[r]-a[l-1]<<"\n"; 17 } 18 return 0; 19 }
2.二维前缀和
令 a 数组 例如a[2][3] 代表 b[1][1]+b[2][1]+b[1][2]+b[2][2]+b[1][3]+b[2][3];
Q：问 b[x1][y1] 到 b[x2][y2] 的和
A : O(NM)，核心步骤：
a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j] 最后 ans = a[x2][y2] - a[x2][y1-1]-a[x1-1][y2] + a[x1-1][y1-1]
#include <bits/stdc++.h> using namespace std; #define ll long long int a[1005][1005],s[1005][1005],n,m,xo,yo,xs,ys,q; int main() { cin>>n>>m>>q; for(int i = 1 ; i <= n ; i++ ) for(int j = 1 ; j <= m ; j++) { cin>>a[i][j]; s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]; } while(q--) { cin>>xo>>yo>>xs>>ys; ll ans = s[ys][xs]-s[yo-1][xs]-s[yo-1][ys]+s[yo-1][xo-1]; cout<<ans<<"\n"; } return 0; }
3.一维差分
令 a 数组 a[i] 代表 b[1]+b[2]+b[3]+…+b[i]
Q： 如果我们想令从 a[l] 到 a[r] 的 值全部加上c(常数)；
A: 暴力循环只能是TLE，但是通过核心步骤：
b[i]+=c , b[r+1] - = c;
实现O（1）解决
以下是代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 ll a[10005],b[10005],l,r,c,n,q; 5 void insert(int l , int r , int c) 6 { 7 b[l]+=c; 8 b[r+1]-=c; 9 } 10 int main() 11 { 12 cin>>n>>q; 13 for(int i = 1 ; i <= n ; i++) 14 { 15 cin>>a[i]; 16 insert(i,i,a[i]); 17 } 18 while(q--) 19 { 20 cin>>l>>r>>c; 21 insert(l,r,c); 22 } 23 //前缀和操作 24 for(int i = 1 ; i <= n ; i++) 25 { 26 a[i]=a[i-1]+b[i]; 27 cout<<a[i]<<" "; 28 } 29 30 return 0;
4.二维差分
令 a 数组 例如a[2][3] 代表 b[1][1]+b[2][1]+b[1][2]+b[2][2]+b[1][3]+b[2][3];
Q : 如果我们想从a[x1][y1] 到 a[x2][y2] 的值全部加上 c（常数）
A : 暴力循环是 O(NM)，核心步骤是：
b[x1][y1]+=c
b[x1][y1+1]-=c
b[x2][y2+1]-=c
b[x2+1][y2+1]+=c
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 ll a[1005][1005],b[1005][1005],c,x,y,x2,y2,n,m,q; 5 6 void insert(int x,int y, int x2, int y2,int c) 7 { 8 b[x][y] += c; 9 b[x][y2+1] -= c; 10 b[x2+1][y] -= c; 11 b[x2+1][y2+1] += c; 12 } 13 14 int main() 15 { 16 cin>>n>>m>>q; 17 for(int i = 1 ; i <= n ; i++) 18 for(int j = 1 ; j <= m ; j++) 19 { 20 cin>>a[i][j]; 21 insert(i,j,i,j,a[i][j]); 22 } 23 while(q--) 24 { 25 cin>>x>>y>>x2>>y2>>c; 26 insert(x,y,x2,y2,c); 27 } 28 for(int i = 1 ; i <= n ; i++) { 29 for (int j = 1; j <= m; j++) { 30 a[i][j] = b[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; 31 cout << a[i][j] << " "; 32 } 33 cout << "\n"; 34 } 35 return 0; 36 }