前缀和
作者:
Khalil.
,
2025-04-27 19:33:07
· 山东
,
所有人可见
,
阅读 1
一维
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], p[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; ++ i)
cin >> a[i];
for(int i = 1; i <= n; ++ i)
p[i] = p[i - 1] + a[i];
while(m --){
int l, r;
cin >> l >> r;
cout << p[r] - p[l - 1] << endl;
}
return 0;
}
二维
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int p[N][N];
int main(){
int n, m, q;
cin >> n >> m >> q;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
cin >> p[i][j];
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
while(q--){
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1] << endl;
}
return 0;
}