前缀和算法详解：如何用空间换时间优化区间查询

1.1.2 最大子段和

关于最大子段和问题，利用前缀和可以高效求解。考虑以 i 位置的元素 a[i] 结尾的最大子段和：

• 在求「区间和」时，相当于用 f[i] 减去 i 位置前面的某一个 f[x]。
• 如果想要「最大子段和」，也就是「最大区间和」，那么用 f[i] 减去一个「前驱最小值」即可。

参考代码：

#include <iostream>
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;
    for (int i = 1; i <= n; i++) {
        ret = max(ret, f[i] - prevmin);
        prevmin = min(prevmin, f[i]);
    }
    cout << ret << endl;
    return 0;
}

1.2 二维前缀和

1.2.1 基础原理

对于二维矩阵，我们需要快速查询某个子矩阵内所有元素的和。

• 暴力模拟：查询哪个子区间，用两层 for 循环累加，时间复杂度高 O(q * n * m)。
• 二维前缀和：快速查询二维数组中的某个子矩阵所有元素和，预处理时间复杂度 O(n * m)，查询时间复杂度 O(1)。

我们定义 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]

查询以 (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;
}

1.2.2 激光炸弹

题目要求若目标位于爆破正方形的边上，该目标不会被摧毁。这意味着如果想尽可能炸更多目标，炸弹边和矩阵边重叠时需要特别注意边界条件。

思路： 暴力枚举坐标系中所有边长为 R 的正方形，找出正方形内目标价值最大的目标即可。我们可以枚举右下角 [x2, y2] 从而得到整个正方形，用一个二维矩阵将所有目标的价值存起来，其中 a[i][j] 就表示 [i, j] 位置的目标价值之和。

参考代码：

#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 开始
        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 << endl;
    return 0;
}

结语

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

掌握前缀和不仅能够解决经典问题，更能为复杂场景（如动态规划、数据结构优化）提供关键思路。其思想可以延伸到更高维度的数据处理中，成为算法设计中不可或缺的'预谋'手段。理解并灵活运用前缀和，是提升算法问题解决能力的重要一步。