一维前缀和

即数列的前n项和。通过前缀和可以在O(1)时间内求出任何一个子区间的和，以下是一个前缀和的示例：

vector<int> v{2, 2, 2, 2, 2, 2, 2, 2, 2, 2};
vector<int> preSum(v.size());
preSum[0] = v[0];
for(int i = 1; i < v.size(); i++) {
    preSum[i] = preSum[i-1] + v[i];
}

要求区间[i, j]的和，只需要应用sum[i, j] = preSum[j] - preSum[i] + v[i]即可。

如果在前缀和前面插入一个0，则求和公式可以进一步简化成sum[i, j] = preSum[j] - preSum[i-1]。


C++提供了std::partial_sum用于求前缀和，它包含在头文件<numeric>中，形式如下：

template <class InputIt, class OutputIt>
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first);

template <class InputIt, class OutputIt, class BinaryOperation>
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first,
                     BinaryOperation op);

计算区间[first, last)的前缀和，并写入到d_first起始的范围，d_first可以等于first，表示直接使用原数组来存储前缀和。第二个版本使用给定的op进行求和。以下是代码示例：

#include <numeric>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v(10, 2);
    vector<int> preSum(10);     // 前缀和，与原数组等大，不插入0前缀
    vector<int> preProduct(10); // 前缀积，通过自定义op实现

    partial_sum(v.begin(), v.end(), preSum.begin());
    for(auto &i : preSum) {
        cout << i << " ";
    }
    cout << endl;

    partial_sum(v.begin(), v.end(), preProduct.begin(), [](int a, int b) { return a * b; });
    for(auto &i : preProduct) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

运行结果：

2 4 6 8 10 12 14 16 18 20
2 4 8 16 32 64 128 256 512 1024

二维前缀和

将前缀和的概念扩展到二维数组，比如对于数组grid，点(x,y)的前缀和就是从(0,0)到(x,y)定义的矩形的和，它的求和公式为：

sum[x][y] =grid[x][y] + sum[x][y-1] + sum[x-1][y] - sum[x-1][y-1]

示意图如下：


求(x1,y1)和(x2,y2)构成的矩形的和，公式为：

area = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]

示意图如下：

二维前缀和示例：

  • 2201. 统计可以提取的工件 - 力扣（LeetCode）
    • 思路：初始化网格为全0，标记被挖掘过的点为1，然后计算网格的前缀和。对每个工件，通过工件的左上和右下坐标可以得到区域内的和，如果这个和等于矩形的面积，则表示这个工件已经全部被挖掘出来了。