算法基础：前缀和如何优化区间查询

在算法设计与优化中，前缀和是一种简单却强大的技巧，能够将复杂问题转化为高效计算。无论是处理一维数组的区间求和，还是解决二维矩阵的子矩阵问题，前缀和都能通过预处理将时间复杂度从线性降低到常数级别，彻底改变问题的解决方式。

前缀和

前缀和与差分的核心思想是预处理。它允许我们在暴力枚举的过程中快速给出查询结果，从而优化时间复杂度。这是一种典型的用空间换时间的策略。

前缀和： 快速求出数组中某一段区间和，单次查询时间复杂度为 O(1)。

1.1 一维前缀和

1.1.1 基础应用

处理区间求和时，如果直接对每个查询进行循环累加，时间复杂度为 O(n * q)，数据量大时极易超时。采用前缀和策略后，我们可以先构建一个辅助数组，将查询操作降至 O(1)。

实现思路：

1. 定义前缀和数组 f[i]，表示原数组区间 [1, i] 中所有元素的和。
2. 递推公式：f[i] = f[i - 1] + a[i]。
3. 查询区间 [l, r] 的和，只需计算 f[r] - f[l - 1]。

这种写法避免了重复计算，逻辑非常清晰。实际编码时注意数组下标通常从 1 开始，方便处理边界情况。

参考代码：

#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;
}

1.1.2 最大子段和

在求解最大子段和问题时，利用前缀和可以进一步优化。考虑以位置 i 的元素 a[i] 结尾的最大子段和：

• 这相当于用 f[i] 减去 i 位置前面的某一个前缀和 f[x]。
• 为了让结果最大，我们需要减去一个尽可能小的 f[x]（即前驱最小值）。

参考代码：

#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 基础应用

当问题扩展到二维矩阵时，我们需要快速计算某个子矩阵内所有元素的和。暴力模拟需要两层循环累加，效率较低。二维前缀和可以将预处理复杂度控制在 O(n * m)，查询复杂度降为 O(1)。

核心原理：

1. 创建前缀和矩阵 f[i][j]，表示从 (1, 1) 到 (i, j) 区域内所有元素的和。
2. 状态转移方程利用了容斥原理： f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + a[i][j] 这里减去 f[i-1][j-1] 是为了避免左上角区域被重复计算。
3. 查询以 (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 的正方形内部（不含边界）价值最大的区域。为了简化处理，通常将正方形视为覆盖范围，并调整坐标偏移。

解题思路：

1. 使用二维数组存储每个坐标点上的目标价值总和。
2. 构建二维前缀和矩阵。
3. 枚举所有可能的边长为 R 的正方形的右下角坐标，利用前缀和公式计算该区域内的总价值。
4. 取最大值作为答案。

注意处理边界情况，例如当 R 大于矩阵维度时，应直接取整个矩阵的价值。

参考代码：

#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; // 同一个位置可能有多个目标
    }

    // 预处理
    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;
    m = min(m, limit); // 如果 m 很大，相当于就是把整个区域全部摧毁

    // 枚举所有边长为 m 的正方形
    for (int x2 = m; x2 <= limit; x2++) {
        for (int y2 = m; y2 <= limit; 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;
}

结语

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

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