前缀和

即数列的前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

页面树结构

前缀和