在需要频繁地求数组中区间的和的情景下，前缀和数组十分有用。花费 $O(n)$ 的时间生成前缀和，之后只需要 $O(1)$ 的时间计算区间和。
定义一个数组a = [1, 2, 3, 4, 5]，它的前缀和数组：
prefix[0] = 1
prefix[1] = 1 + 2 = 3
prefix[2] = 1 + 2 + 3 = 6
prefix[3] = 1 + 2 + 3 + 4 = 10
prefix[4] = 1 + 2 + 3 + 4 + 5 = 15
要计算 $[i,j]$ 区间的和，可以用 prefix[j] - prefix[i-1] 算出，其中 i = 0 下溢时直接取 prefix[j]。
vector<int> prefix(n);
int sum = 0;
for(int i = 0; i < n; i++) {
sum += i;
prefix[i] = sum;
}
C++的numeric库提供了一个方便的函数partial_sum可以快速计算前缀和。
vector<int> arr[n], prefix(n);
for(int i=0;i<n;i++) cin >> arr[i];
partial_sum(arr.begin(), arr.end(), prefix.begin());
Practice: CF-1398C
Codeforce例题 C. Good Subarrays
对于一个数组，有多少子数组符合条件：子数组内所有元素相加等于子数组的长度。
- 当遇到数字0，区间长度增加但区间的和不变，此时对区间的影响为-1
- 当遇到数字1，区间长度加1，但需要额外一个元素来填充，此时对区间的影响为0
- 当遇到数字x，此时对区间的影响为 x-1
我们所要寻找的subarray，则是区间的影响为0的。
比如 120 这三个数，如果每位减1，可以得到 0 1 -1
如果使用一维循环就能发现：
- 0 符合，则$a_{1...1}$ 是好数组
- 0 + 1 + -1 也符合，则$a_{1...3}$ 也是好数组。
但是如果要发现 $a_{2...3}$ (1 + -1) 也是好数组，则需要了解另一个trick。
这道题的本质是寻找出相加和等于 x 的子数组数量。
$prefix[i]-prefix[j]=x$
$prefix[j]=prefix[i]-x$
我们希望统计出截至对于任意的 i 的所有相加和为 x 的子数组数量。
对于每个 $prefix[i]$， 只需要统计之前有多少个 $prefix[j]$ 存在，实际上就是统计有多少个 $prefix[i]-x$ 存在。
因此我们总是先定义一个哈希表
将之前存在的 $prefix[j]$ 的数量加进答案
将当前的sum记录下来
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
string a;
int n; cin >> n >> a;
long long ans = 0, sum = 0;
map<int, int> mp;
for(int i=0;i<n;i++) {
sum += a[i] - '0' - 1;
if(sum==0) ans++;
ans += mp[sum];
mp[sum]++;
}
cout << ans << endl;
}
return 0;
}
差分
差分可以看作是前缀和的逆运算。
a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。
则满足，a[i] = b[1] + b[2]+ b[3] +,,,,,, + b[i]
b[1] = a[1] - a[0]
b[2] = a[2] - a[1]
b[n] = a[n] - a[n-1]
给a数组中的[l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] -= c。时间复杂度为O(1), 大大提高了效率。
Prefix XOR
pass
前缀积
pass
writing started at 2025-02-08 19:22, ended 2025-05-04
Refs