一维前缀和
输入样例
5 3 //数列总数 查询次数
2 1 3 6 4 //输入数列
1 2 //查询坐标
1 3
2 4
输出样例
3
6
10
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5 + 10;
int num[N], sum[N];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)//从1开始较为方便
scanf("%d", &num[i]);
for (int i = 1; i <= n; i++)//求出前缀和
{
if (i == 1)
sum[i] = num[i];
else
sum[i] = sum[i - 1] + num[i];
}
while (m--)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", sum[r] - sum[l - 1]);
}
return 0;
}
二维前缀和
输入样例
3 4 3 //矩阵行数 矩阵列数 查询次数
1 7 2 4 //输入矩阵元素
3 6 2 8
2 1 2 3
1 1 2 2 //查询坐标x1,y1,x2,y2
2 1 3 4
1 3 3 4
输出样例
17
27
21
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int num[N][N], sum[N][N];
int main()
{
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)//从1开始较为方便
for (int j = 1; j <= m; j++)
scanf("%d", &num[i][j]);
for (int i = 1; i <= n; i++)//求出前缀和
for (int j = 1; j <= m; j++)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + num[i][j];
while (q--)//询问
{
int x1, x2, y1, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]);
}
return 0;
}