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