Part1.1 一维前缀和
题目描述
输入一个长度为 \(n\) 的整数序列，接下来输入 \(m\) 个询问，每个询问输入一对 \(l\) , \(r\)
对于每个询问，输出原序列中从第 \(l\) 个数到第 \(r\) 个数的和
输入格式
第一行包含两个整数 \(n\) 和 \(m\)
第二行包含 \(n\) 个整数，表示整数序列
接下来 \(m\) 行，每行包含 \(2\) 个整数 \(l\) 和 \(r\)，表示一个询问的区间范围
输出格式
共 \(m\) 行，每行输出一个询问的结果
数据范围
\(1\) \(\leq\) \(l\) \(\leq\) \(r\) \(\leq\) \(n\)
\(1\) \(\leq\) \(n\) , \(m\) \(\leq\) \(100000\)
−\(1000\) \(\leq\) 数列中元素的值 \(\leq\) \(1000\)
思路
定义 \(a\) 数组表示整数序列
\(b\) 数组表示 \(a\) 数组的前缀和
于是就有
int a[6] = {0,1,2,3,4,5};
int b[6] = {0,1,3,6,10,15};
可以发现
前缀和就是从位置 \(1\) 到位置 \(i\) 这个区间内的所有的数字之和
b[i] = a[1] + a[2] + ...+a[i]
又有
b[l] = a[1] + a[2] + ... + a[l];
b[r] = a[1] + a[2] + ... + a[l] + a[l+1] + a[l+2] + ... + a[r];
即
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N], b[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
b[i] = b[i - 1] + a[i];
}
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &l, &r);
printf("%d", b[r] - b[l - 1]);
}
return 0;
}
Part1.2 习题
Part2.1 二维前缀和
题目描述
输入一个 \(n\) 行 \(m\) 列的整数序列，再输入 \(k\) 个询问，每个询问包括 \(4\) 个整数 \(x_1\) , \(y_1\) , \(x_2\) , \(y_2\) ，表示一个子矩阵的左上角和右下角坐标
输入格式
第一行包含 \(3\) 个整数 \(n\) , \(m\) , \(k\)
接下来 \(n\) 行，每行包含 \(m\) 个整数，表示整数矩阵
接下来 \(k\) 行，每行包含 \(4\) 个整数 \(x_1\) , \(y_1\) , \(x_2\) , \(y_2\) ，表示一组询问
输出格式
共 \(k\) 行，每行输出 \(1\) 个询问的结果
数据范围
\(1\) \(\leq\) \(n\) , \(m\) \(\leq\) \(1000\)
\(1\) \(\leq\) \(k\) \(\leq\) \(200000\)
\(1\) \(\leq\) \(x_1\) \(\leq\) \(x_2\) \(\leq\) \(n\)
\(1\) \(\leq\) \(y_1\) \(\leq\) \(y_2\) \(\leq\) \(m\)
−\(1000\) \(\leq\) 矩阵内元素的值 \(\leq\) \(1000\)
思路
二维前缀和是基于一维前缀和的，我们要求一个矩阵内一个任意的子矩阵的数的和
定义 \(s[i][j]\) 数组表示从 \((1, 1\)) 到 \((i, j)\) 构成矩阵内数的和
\(map[i][j]\) 即矩阵元素
公式
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, m, k;
int x1, y1, x2, y2;
int map[N][N], s[N][N];
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &map[i][j]), s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + map[i][j];
for (int i = 1; i <= k; i++)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int l = s[x2][y2] + s[x1-1][y1-1] - s[x1-1][y2] - s[x2][y1-1];
printf("%d\n", l);
}
return 0;