版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
一维前缀和
即数列的前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]
示意图如下:
Image Added
求(x1,y1)和(x2,y2)构成的矩形的和,公式为:
area = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]
示意图如下:
Image Added
二维前缀和示例:
- 2201. 统计可以提取的工件 - 力扣(LeetCode)
- 思路:初始化网格为全0,标记被挖掘过的点为1,然后计算网格的前缀和。对每个工件,通过工件的左上和右下坐标可以得到区域内的和,如果这个和等于矩形的面积,则表示这个工件已经全部被挖掘出来了。
目录 |
---|