前缀和
作用：快速求区间和
公式:$s[i]=s[i-1]+a[i]$,其中$s[i]$表示前$i$项的和
例：给定一个$n$项的数列$a$，共$m$次询问，每次询问给出两个数$l,r$，求区间$[l,r]$的和
分析：区间$[l,r]$的和即为前$r$项的和减去前$l-1$项的和，即$s[r]-s[l-1]$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int s[N];
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> s[i];
s[i]+=s[i-1];
}
for(int i=1;i<=m;i++){
int l,r;
cin >> l >> r;
cout << s[r]-s[l-1] << endl;
}
return 0;
}
|
二维前缀和
用$s[i][j]$表示前$i$行每行的前$j$个数之和
$s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]$
例：给定一个$n*n$的矩阵，求最大子矩阵和
分析：左上角为$(x_1,y_1)$,右下角为$(x_2,y_2)$的矩阵和为$s[x_2][y_2]-s[x_1-1][y_2]-s[x_2][y_1-1]+s[x_1-1][y_1-1]$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<bits/stdc++.h>
using namespace std;
const int N=105;
int n;
int s[N][N];
int ans=-1e9;
int sum(int a,int b,int c,int d){
return s[c][d]-s[a-1][d]-s[c][b-1]+s[a-1][b-1];
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin >> s[i][j];
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
for(int x_1=1;x_1<=n;x_1++){
for(int y_1=1;y_1<=n;y_1++){
for(int x_2=x_1;x_2<=n;x_2++){
for(int y_2=y_1;y_2<=n;y_2++){
ans=max(ans,sum(x_1,y_1,x_2,y_2));
}
}
}
}
cout << ans;
return 0;
}
|