当前位置：首页 > news >正文

【算法】前缀和

news 来源：原创 2025/6/17 4:58:23

前缀和

1.【模板】前缀和
2.最大子段和
3.【模板】二维前缀和
4.激光炸弹

前缀的核心思想是预处理，可以在暴力枚举的过程中，快速查询出某一段区间内的和，从而优化时间复杂度。是经典的用空间替换时间的做法。

1.【模板】前缀和

【模板】前缀和

在这里插入图片描述

解法：前缀和

前缀和模板题，直接套用「公式」创建前缀和数组，然后利用前缀和数组的「性质」处理 q 次查询。

创建前缀和数组：f[i] = f[i − 1] + a[i]。

在这里插入图片描述
2. 查询 [l, r] 区间和：f[r] − f[l − 1]。

在这里插入图片描述

#include<iostream>
using namespace std;typedef long long LL;const int N = 1e5 + 10;int n, q;
LL a[N];
LL f[N];  //前缀和数组int main()
{cin >> n >> q;for(int i = 1; i <= n; i++) cin >> a[i];//预处理前缀和数组for(int i = 1; i <= n; i++){f[i] = f[i - 1] + a[i];}//处理 q 次查询while(q--){int l, r;cin >> l >> r;cout << f[r] - f[l - 1] << endl;}return 0;
}

2.最大子段和

P1115 最大子段和

在这里插入图片描述

解法：前缀和

考虑以 i 位置的元素 a[i] 「为结尾」的最大子段和：

在求「区间和」时，相当于是用 f[i] 减去 i 位置前面的某一个 f[x]。
如果想要「最大子段和」，也就是「最大区间和」，那么用 f[i] 减掉一个「前驱最小值」即可。因此，我们可以创建 a 数组的「前缀和」数组，然后在遍历前缀和数组的过程中，一边「更新前驱最小值」，一边「更新当前位置为结尾的最大子段和」。

#include <iostream>
using namespace std;const int N = 2e5 + 10;int n;
int f[N];  //前缀和数组 int main()
{cin >> n;//预处理前缀和数组 for(int i = 1; i <= n; i++){int x; cin >> x;f[i] = f[i - 1] + x;}int ret = -0x3f3f3f3f;int prevmin = 0;//处理最大子段和 for(int i = 1; i <= n; i++){ret = max(ret, f[i] - prevmin);prevmin = min(prevmin, f[i]);}cout << ret << endl;return 0;
}

3.【模板】二维前缀和

【模板】二维前缀和

在这里插入图片描述

解法：前缀和

二维前缀和模板题，直接套用「公式」创建前缀和矩阵，然后利用前缀和矩阵的「性质」处理 q 次查询。

创建前缀和矩阵：f[i][j] = f[i − 1][j] + f[i][j − 1] − f[i − 1][j − 1] + a[i][j]。

在这里插入图片描述

查询以 (x1, y1) 为左上角，(x2, y2) 为右下角的子矩阵的和。

在这里插入图片描述

#include<iostream>
using namespace std;typedef long long LL;const int N = 1e3 + 10;int n, m, q;
LL f[N][N];  //前缀和矩阵int main()
{cin >> n >> m >> q;//预处理前缀和矩阵for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){int x; cin >> x;f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + x;}}//处理 q 次查询while(q--){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;cout << f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1] << endl;}return 0;
}

4.激光炸弹

P2280 [HNOI2003] 激光炸弹

在这里插入图片描述

解法：前缀和

可以用一个二维矩阵将所有目标的价值存起来，其中 a[i][j] 就表示 [i, j] 位置的目标价值之和。一颗炸弹能够获得的价值正好是一个 R × R 大小的一个正方形内所有目标的价值总和，那么我们可以求出 a 矩阵的前缀和矩阵，然后枚举所有边长为 R 的子正方形的价值之和，求出里面的最大值即可。

如何枚举边长为 R 的所有正方形：

仅需枚举右下角 [x2, y2]，那么结合边长 R 就可算出左上角 [x2 − R + 1, y2 − R + 1]。
代入前缀和矩阵中，就可以快速求出这个正方形内所有目标的总价值。

细节问题：

题目中某一个位置会「重复」出现，因此 a[i][j] += w。
半径 R 可能「超过 5000 」，此时炸弹可以摧毁所有目标，也就是整个矩阵的目标价值之和。

#include <iostream>
using namespace std;const int N = 5e3 + 10;int n, m;
int a[N][N];
int f[N][N];  //前缀和矩阵 int main()
{cin >> n >> m;while(n--){int x, y, v; cin >> x >> y >> v;x++; y++;  //从下标为 1 开始计数 a[x][y] += v;  //同一个位置有可能有多个目标 }n = 5001;//预处理前缀和矩阵 for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];}}int ret = 0;m = min(m, n);  //如果 m 很大，相当于就是将整个区域全部摧毁了 //枚举所有边长为 m 的正方形 for(int x2 = m; x2 <= n; x2++){for(int y2 = m; y2 <= n; y2++){int x1 = x2 - m + 1, y1 = y2 - m + 1;ret = max(ret, f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1]);}}cout << ret;return 0;
}