算法基础：前缀和技巧与区间求和优化

扩展应用：最大子段和

在经典的最大子段和问题中，我们同样可以利用前缀和来优化。如果以位置 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 的正方形区域内摧毁价值最大的目标。

注意点：

1. 题目规定若目标位于爆破正方形的边上不会被摧毁，因此实际有效范围是边长为 R 的区域内部。
2. 坐标可能很大，但目标数量有限，或者网格大小固定。本题中网格上限为 5000。
3. 多个目标可能位于同一坐标，需累加价值。
4. 枚举正方形右下角 (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;
}

总结

前缀和作为一种基础而强大的算法技巧，通过预处理数据将复杂度从线性降至常数级别，彻底改变了处理区间问题的方式。从一维数组的快速求和、最大子段和优化，到二维矩阵的区域统计，前缀和以空间换时间的策略展现了极高的效率。

掌握前缀和不仅能够解决经典问题，更能为复杂场景（如动态规划、数据结构优化）提供关键思路。理解并灵活运用前缀和，是提升算法问题解决能力的重要一步。