前缀和笔记
前缀和定义
前缀和(Prefix Sum)是一种重要的预处理技术,能在O(1)时间内查询区间和,在算法竞赛和面试中应用广泛。以下是前缀和的主要应用场景和变种:
1. 基本前缀和
计算$\Sigma_{i=1}^n a_i$的值,用来求区间和
例如:1
2
3
4
5
6
7// 一维前缀和
vector<int> pre(n+1, 0);
for (int i = 1; i <= n; i++) {
pre[i] = pre[i-1] + a[i];
}
// 查询区间[l, r]的和
int sum = pre[r] - pre[l-1];
2. 二维前缀和
用于计算矩阵的和
1 | vector<vector<int>> pre(m+1, vector<int>(n+1, 0)); |
前面两个的例题比较多,则行里就不举例了。
3. 前缀和与哈希表结合
这是最常用的变种,用于解决”区间和为k的区间个数”问题:
1 | int countSubarrays(vector<int>& nums,int k) { |
上面的代码思路解释,首先,先计算前缀和的值,然后加到map里面,之后看有没有出现过sum-k这种前缀和,如果有,那么这一段的和就是k了,且有$mp[sum-k]$个,这样就计算出了答案
例如:K-大师和他的领域
这一题要我们找存在几个区间满足既含有k又满足k是这个区间的中位数。
那么步骤:
1.令小于k的为-1,大于k的为1,等于k的为0
2.计算前缀和,统计前缀和一样的区间,这样区间内的和为0,说明k是这个区间的中位数,再使用$\Sigma{i=1}^{map.size()}C{m_i}^2$计算总数就行了,这样得到可能的区间。
3.但是还要保证区间内包含k,所以找到k位置,在两个k间的需要再用相同方法计算一次,
4.最后减去即可
就是说,要统计合法区间时,都可以把题目的要求变形一下,然后就可以使用这个思路了
4. 前缀和与差分数组
差分数组用于区间修改,单点查询:
这一个没什么好说的,就是差分和前缀的互逆关系
1 | // 初始化差分数组 |
5. 前缀最大/最小值
1 | // 前缀最大值 |
6. 前缀异或和
用于处理区间异或问题:
1 | vector<int> xorPre(n+1, 0); |
7.二维差分数组
1 | // 初始化二维差分 |
然后很重要的一点是,有时可能是假设前缀和数组,最后再反推原数组来进行构造。
https://zestfulyk.github.io/ZestfulYK-blog/2025/12/08/%E5%89%8D%E7%BC%80%E5%92%8C%E7%AC%94%E8%AE%B0/
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 ZestfulYK的Blog!