Part1 定义
前缀和可以简单理解为 "数列的前n项的和"
它是一种重要的预处理方式, 能大大降低查询的时间复杂度.
一般来讲, 我们会预处理一个数组。对数组中每个元素, 我们记录从起始到该元素对应下标/状态所有数字的总和.
一维前缀和
给定一个长度为\(n\) 的数组 \(a\), 预处理一个 \(f\) 数组作为前缀和, 即
\[f_i = \sum_{j=1}^{i} a_j = a_1 + a_2 + \cdots + a_i
\]
二维前缀和
给定一个 \(n \times m\) 的数组 \(a\), 预处理一个 \(f\) 二维数组作为前缀和, 即
\[f_{i, j} = \sum_{k=1}^{i} \sum_{l=1}^{j}a_{k, l} = a_{1, 1} + a_{1, 2} + a_{1, j} + a_{2, 1} +\cdots + a_{i, j}
\]
多维前缀和
可以类推
Part2 实现方式
一维前缀和
一般可以在线性时间内解决, 枚举 \(1-n\), 有公式
\[f_i = f_{i-1} + a_i
\]
二维前缀和
枚举 \(1-n\), \(1-m\), 有公式
\[f_{i, j} = f_{i-1, j} + f_{i, j-1} - f_{i-1, j-1} + a_{i, j}
\]
多维前缀和
可以使用容斥计算
Part3 Code
一维前缀和
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N], f[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
f[i] = f[i - 1] + a[i];
}
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &l, &r);
printf("%d", f[r] - f[l - 1]);
}
return 0;
}
二维前缀和
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, m, k;
int x1, y1, x2, y2;
int a[N][N], f[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", &a[i][j]), f[i][j] = f[i][j-1] + f[i-1][j] - f[i-1][j-1] + a[i][j];
for (int i = 1; i <= k; i++)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int l = f[x2][y2] + f[x1-1][y1-1] - f[x1-1][y2] - f[x2][y1-1];
printf("%d\n", l);
}
return 0;