【前缀和】

前缀和可以简单理解为“数列的前 n 项的和”，它是一种重要的预处理方式，能大大降低查询的时间复杂度。在 C++ 中，标准库中实现了前缀和函数 std::partial_sum，定义于头文件<numeric>中。

示例：

题目:

有 n 个正整数放到数组 a 里，现在要求一个新的数组 b，新数组的第 i 个数 b[i]是原数组 a 第 0 到第 i 个数的和。

输入：

1 2 5

输出：

1 3 8

解题思路：

递推公式为 b(0)=a(0)，对于 i>0 则 b(i)=b(i-1)+a(i) 。

参考代码：

#include <iostream>

int main() {
    int n, a[10000], b[10000];
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    // 前缀和数组的第一项和原数组的第一项是相等的
    b[0] = a[0];
    for (int i = 1; i < n; i++) {
        // 前缀和数组的第 i 项 = 原数组的 0 到 i-1 项的和 + 原数组的第 i 项
        b[i] = b[i - 1] + a[i];
    }
    for (int i = 0; i < n; i++) {
        std::cout << b[i] << " ";
    }
    return 0;
}

在上述代码中，首先输入数组 a 的元素个数 n 以及各个元素的值。然后通过循环计算前缀和数组 b，其中 b[0]等于 a[0]，之后的 b[i]等于 b[i - 1]加上 a[i]。最后输出前缀和数组 b 的所有元素。

二维/多维前缀和：

多维前缀和的普通求解方法几乎都是基于容斥原理。例如将一维前缀和扩展到二维前缀和，假设有一个矩阵（可视为二维数组）：

1 2 3

1 2 4

3 5 1

定义一个矩阵 sum，使得 sum[i][j]表示从左上角（0，0）到（i，j）位置的元素之和。那么这个矩阵 sum 如下所示：

1 3 6

2 5 11

5 10 17

递推求 sum 的过程为：sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]。因为同时加了 sum[i - 1][j]和 sum[i][j - 1]，故重复了 sum[i - 1][j - 1]，需要减去。

其应用例如求子矩阵的和，若要求左上角为（x1，y1）、右下角为（x2，y2）的子矩阵的和，根据类似的思考过程，可得答案为sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]。

二维前缀和的参考代码如下：

#include <iostream>

int main() {
    int n, m;
    std::cin >> n >> m;
    int a[103][103], b[103][103]; // 前缀和数组，相当于上文的 sum()
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> a[i][j];
            b[i][j] = b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + a[i][j]; // 求前缀和
        }
    }
    int ans = 0;
    int l = 1;
    while (l <= std::min(n, m)) { // 判断条件
        for (int i = l; i <= n; i++) {
            for (int j = l; j <= m; j++) {
                if (b[i][j] - b[i - l][j] - b[i][j - l] + b[i - l][j - l] == l * l) {
                    ans = std::max(ans, l); // 在这里统计答案
                }
            }
        }
        l++;
    }
    std::cout << ans << std::endl;
    return 0;
}

上述代码中，首先输入矩阵的行数 n 和列数 m，然后输入原始矩阵 a 的元素值。通过两层循环计算前缀和矩阵 b，接着使用嵌套的四层循环来判断每个可能的边长为 l 的正方形子矩阵的元素和是否等于 l 的平方，如果是，则更新最大正方形的边长 ans。最后输出最大正方形的边长。

基于 dp（动态规划）计算高维前缀和的方法，即通常语境中所称的高维前缀和。设高维空间共有 d 维，需要对数组 a 求高维前缀和 s。令 s[k][i1][i2]...[id]表示同 a[k + 1][i1 + 1][i2 + 1]...[id + 1]后 d 点高维前缀和的贡献。由定义可知 s[0][i1][i2]...[id] = a[0][i1][i2]...[id]，以及 s[k][0][0]...[0] = 0（0 <= k < n）。