算法基础：前缀和技巧与区间求优化
在算法设计与性能优化中，前缀和（Prefix Sum）是一种简单却极具威力的技巧。它通过预处理数据，将原本需要线性遍历的区间求和问题转化为常数时间的查询，实现了典型的'空间换时间'策略。无论是处理一维数组的区间累加，还是解决二维矩阵的子区域统计，掌握前缀和都能显著提升代码效率。
本文将深入探讨一维和二维前缀和的核心原理、实现细节及典型应用场景，帮助你理解这一基础算法如何在竞赛与工程实践中改变问题的复杂度格局。
一维前缀和
核心原理
对于静态数组的多次区间求和查询，暴力模拟每次遍历的时间复杂度高达 O(n*q)，极易超时。前缀和通过预先计算每个位置之前的累加和，将单次查询降至 O(1)。
定义前缀和数组 f，其中 f[i] 表示原数组 a 从下标 1 到 i 的元素之和。递推公式如下：
f[i] = f[i - 1] + a[i]
当需要查询区间 [l, r] 的和时，利用容斥原理，结果即为：
sum(l, r) = f[r] - f[l - 1]
注意：通常为了处理边界情况方便，数组下标从 1 开始，且 f[0] 初始化为 0。
代码实现
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
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;
}
扩展应用：最大子段和
在经典的最大子段和问题中，我们同样可以利用前缀和来优化。如果以位置 i 结尾的最大子段和已知，那么该值等于 f[i] 减去 i 之前所有前缀和中的最小值。
思路是维护一个变量记录当前遇到的最小前缀和 prevmin，遍历过程中不断更新答案 ret。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n;
LL f[N]; // 前缀和数组
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
LL x;
cin >> x;
f[i] = f[i - 1] + x;
}
LL ret = -1e20; // 初始化为极小值
LL prevmin = 0; // 前缀和最小值，初始为 f[0]=0
for (int i = 1; i <= n; i++) {
ret = max(ret, f[i] - prevmin);
prevmin = min(prevmin, f[i]);
}
cout << ret << endl;
return 0;
}
二维前缀和
核心原理
当问题扩展到二维矩阵时，我们需要快速计算任意子矩阵的元素和。暴力枚举子矩阵内所有元素的时间复杂度为 O(qnm)，依然无法接受。
定义二维前缀和数组 f[i][j]，表示从左上角 (1, 1) 到右下角 (i, j) 所围成的矩形区域内所有元素的和。
预处理公式：
f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j]
这里减去 f[i - 1][j - 1] 是因为它在加上第一行和第二列时被重复计算了一次。
查询公式：
对于以 (x1, y1) 为左上角，(x2, y2) 为右下角的子矩阵，其和为：
sum = f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1]
这同样是容斥原理的应用：大矩形减去上方和左侧的矩形，再加上被多减一次的左上角重叠部分。
代码实现
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1010;
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++) {
LL 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;
}
实战案例：激光炸弹
在实际场景中，二维前缀和常用于解决覆盖类问题。例如'激光炸弹'题目要求在一个 R*R 的正方形区域内摧毁价值最大的目标。
注意点：
- 题目规定若目标位于爆破正方形的边上不会被摧毁，因此实际有效范围是边长为 R 的区域内部。
- 坐标可能很大，但目标数量有限，或者网格大小固定。本题中网格上限为 5000。
- 多个目标可能位于同一坐标，需累加价值。
- 枚举正方形右下角
(x2, y2)，左上角自然确定为(x2 - R + 1, y2 - R + 1)。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
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-based 索引
a[x][y] += v; // 同一点价值累加
}
// 预处理前缀和
// 注意：题目中 n 和 m 是输入的目标数，但网格大小可能更大，这里统一按 5001 处理
int limit = 5001;
for (int i = 1; i <= limit; i++) {
for (int j = 1; j <= limit; j++) {
f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
}
}
int ret = 0;
// 确保边长不超过网格实际范围
int side = min(m, limit);
// 枚举所有可能的边长为 side 的正方形
for (int x2 = side; x2 <= limit; x2++) {
for (int y2 = side; y2 <= limit; y2++) {
int x1 = x2 - side + 1;
int y1 = y2 - side + 1;
ret = max(ret, f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1]);
}
}
cout << ret << endl;
return 0;
}
总结
前缀和作为一种基础而强大的算法技巧，通过预处理数据将复杂度从线性降至常数级别，彻底改变了处理区间问题的方式。从一维数组的快速求和、最大子段和优化，到二维矩阵的区域统计，前缀和以空间换时间的策略展现了极高的效率。
掌握前缀和不仅能够解决经典问题，更能为复杂场景（如动态规划、数据结构优化）提供关键思路。理解并灵活运用前缀和，是提升算法问题解决能力的重要一步。