前缀和学习笔记
1. 前缀和概述
前缀和是一种预处理技术，通过预先计算数组中从第一个元素到当前元素的累加和，来优化区间查询操作。
2. 一维前缀和
2.1 基本实现
1
2
3
4
5
6
7
8
9
10
11
12
|
void buildPrefixSum(int nums[], int n, int preSum[]) {
preSum[0] = 0;
for(int i = 0; i < n; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
}
int rangeSum(int preSum[], int left, int right) {
return preSum[right + 1] - preSum[left];
}
|
2.2 经典例题
- P8218 【深进1.例1】求区间和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int n, m;
int a[100005], s[100005];
s[0] = 0;
for(int i = 1; i <= n; i++) {
s[i] = s[i-1] + a[i];
}
while(m--) {
int l, r;
cin >> l >> r;
cout << s[r] - s[l-1] << endl;
}
|
这是一道非常基础的前缀和模板题，帮助理解前缀和的基本概念和实现。题目直接考察区间查询，是前缀和最基本的应用。
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<bits/stdc++.h>
using namespace std;
int n,a[100100],m,c,d,sum=0,b[100010];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=b[i-1]+a[i];
}
cin>>m;
for(int i=0;i<m;i++)
{
cin>>c>>d;
cout<<b[d]-b[c-1]<<endl;
}
return 0;
}
|
3. 二维前缀和
3.1 基本实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void build2DPrefixSum(int matrix[][1005], int m, int n, int preSum[][1005]) {
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
preSum[i][j] = 0;
}
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
preSum[i + 1][j + 1] = preSum[i + 1][j] + preSum[i][j + 1]
- preSum[i][j] + matrix[i][j];
}
}
}
int getRegionSum(int preSum[][1005], int x1, int y1, int x2, int y2) {
return preSum[x2 + 1][y2 + 1] - preSum[x2 + 1][y1]
- preSum[x1][y2 + 1] + preSum[x1][y1];
}
|
4. 前缀和的应用场景
4.1 适用情况
- 需要频繁查询区间和
- 数组元素不会被修改
- 对查询速度要求高
4.2 复杂度分析
- 预处理时间复杂度：O(n)
- 查询时间复杂度：O(1)
- 空间复杂度：O(n)
5. 进阶应用
5.1 差分数组
差分数组是前缀和的逆运算，常用于区间修改操作。
5.2 前缀和的变种
- 前缀积
- 异或前缀和
- 前缀最大值/最小值
6. 练习题目推荐
- P1115 最大子段和 - 一维前缀和的基础应用
- P1387 最大正方形 - 二维前缀和的经典题目
- P2671 求和 - 前缀和的进阶运用
- P1719 最大加权矩形 - 二维前缀和与最大子矩阵和
- P3397 地毯 - 二维差分数组的应用
7. 注意事项
- 构建前缀和数组时，通常多开一个位置（下标0）
- 注意数组下标的处理，特别是区间和的计算
- 处理大数据时注意整型溢出问题
- 使用数组时要预先定义足够大的空间
