例 1展开目录
给定一个长度为 N 的数组:$A_1,A_2,...,A_N$(N <= 100000,1 <= A [i] <= 100000)。然后有 M 个询问,每次询问给两个整数 L,R,问 A [L]~A [R] 的和是多少。(M <= 100000)
这道题最直接的做法就是每次询问的时候,用一个循环累加 A [L]~A [R] 的和,伪代码如下:
- Ask(L,R)
- Sum = 0
- For i = L...R
- Sum += A[i]
- return Sum
上面这段伪代码,处理一个询问的时间复杂度是 O (R-L),考虑到 R 最大是 N,L 最小是 1,所以可以认为是 O (N)。而通过前缀和,我们可以把每次询问的复杂度降到 O (1)
思路展开目录
假设我们有这么一个数组:$A=[A_1, A_2,...,A_N]$。我们将 A [i] 加到 A [j] 的和称为部分和,记作 S [i,j],上面的题目就是询问 M 次部分和。为了减少计算部分和的复杂度,我们先计算出前缀和:S [i] = A [1] + A [2] + ... + A [i]。前缀和可以通过递推的方法 O (N) 求出来
- S[0] = 0
- For i = 1...N
- S[i] = s[i-1] + A[i]
我们看下图,第一排 [1,2,5,4,3] 是 A 数组,第二排 [0,1,3,8,12,15] 就是前缀和。当我们有了前缀和,想要计算 S [i,j] = A [i] + A [i+1] + ... + A [j] 的时候,直接用 S [j] - S [i-1] 就行了,比如我们要算 A [2]+A [3]+A [4] = 2+5+4=11,只要算 S [4]-S [1]=12-1=11 即可
所以我们利用前缀和就可以把计算部分和的复杂度降到 O (1),只用计算一次减法。注意 A 数组是从下标 1 开始的,但是前缀和数组是从下标 0 开始的,并且 S [0] 的值 0。这样可以在计算从 $A_1$ 开始的部分和时也不会出问题,例如 $A_1+A_2+A_3=S [3]-S [0] = 8-0=8$
例 2 K 倍区间展开目录
思路 1 暴力枚举展开目录
- Ans = 0
- For i = 1...N
- For j = i...N
- Sum = 0
- For p = i...j
- Sum += A[p]
- If Sum % k == 0
- Ans++
这个算法的时间复杂度是 $O (N^3)$
思路 2 前缀和优化展开目录
优化的思路就是先把部分和,转换成前缀和的差。题目要求 A [i]+A [i+1]+…+A [j] 是 K 的倍数,等价于 S [j]-S [i-1] 是 K 的倍数,等价于 S [j] 与 S [i-1] 模 K 余数相等。所以我们可以还是 2 重循环枚举 i 和 j,但是直接用前缀和判断是不是 K 的倍数:
- Ans = 0
- For i = 1...N
- For j = i...N
- If (S[j] - S[i - 1]) % k == 0
- Ans++
优化之后的复杂度是 $O (N^2)$,还不足够优秀,还是会超时。我们再进一步分析一下要求的答案和前缀和的关系,看一下下面这张图
图中的第一排 [1, 2, 5, 4, 3] 是 A 数组。绿色的第二排是前缀和,天蓝色的第三排是前缀和 % K 之后的结果,这里我们假设 K=2。
我们之前的算法,实际上就是在第三排的数组里,找两个相等的值(这里解释一下为什么是找相等的值,因为如果两个值相等,那么 s [j] - s [i-1]=0,0% k=0)。每一对相等的值,都对应着一个 K 倍区间。比如第三排有 3 个 0,第一个 0 和第二个 0,对应 [1, 2, 5] 这个区间;第一个和第三个 0,对应 [1, 2, 5, 4] 这个区间;第二个和第三个 0,对应 [4] 这个区间
所以我们已知第三排数组有 3 个 0 和 3 个 1 的情况下,可以直接用组合数求出来 K 倍区间的数目:C (3,2)+C (3, 2)=6。其中 C (3, 2) 是指从 3 个物品里取出 2 个来的组合数。因为有 3 个 0 和 3 个 1,所以答案就是 C (3, 2)+C (3, 2)
把上面统计的思路归纳一下,就是:计算前缀和 S [0], S [1], S [2], … S [N]。统计 S [] 中模 K 余 0, 1, 2 … K-1 的数量,记为 cnt [0], cnt [1], cnt [2] … cnt [K-1]。最终答案就是:
$$ cnt[0]\times \frac{cnt[0]-1}{2} + cnt[1]\times \frac{cnt[1]-1}{2}+...+cnt[k-1]\times \frac{cnt[k-1]-1}{2} $$
- #include <iostream>
- #include <unordered_map>
- using namespace std;
- int n,k,a[100001],s[100001];
- unordered_map<int,int> cnt;
- //cnt[0]存储的是余数是0的前缀和有几个
- //cnt[1]存储的是余数是1的前缀和有几个
- //以此类推
- int main()
- {
- cin >> n >> k;
- for(int i = 1;i <= n;i++)
- cin >> a[i];
- s[0] = 0;
- cnt[0] = 1;
- for(int i = 1;i <= n;i++)
- {
- s[i] = (s[i-1] + a[i]) % k;
- cnt[s[i]]++;
- //一边求前缀和
- //一边统计前缀和模K的余数出现了多少次
- }
- long long ans = 0;
- //根据每个余数出现的次数用组合数求答案
- for(int i = 0;i < k;i++)
- ans += (long long)(cnt[i]) * (cnt[i] - 1) / 2;
- //把答案累加上C(cnt[i], 2)
- //也就是cnt[i]*(cnt[i]-1)/2
- cout << ans;
- return 0;
- }
上面的程序既用到了前缀和优化,也用了哈希表统计每个前缀和余数出现的次数。总复杂度是 $O (N+K)$
例 3 K 的倍数展开目录
我们要找到最长的 K 倍区间。实际上就是找到前缀和余数最左边和最右边的 0 的位置,算一下长度;再找到最左边和最右边的 1 的位置,算一下长度…… 最后找到最左边和最右边 K-1 的位置,算一下长度。最终取其中最长的区间就是答案
- #include <iostream>
- #include <unordered_map>
- using namespace std;
- int n,k,a[100001],s[100001];
- unodered_map<int.int>lmost.rmost;
- int main()
- {
- cin >> n;
- for(int i = 1;i <= n;i++)
- cin >> a[i];
- cin >> k;
- for(int i = 1;i <= n;i++)
- {
- lmost[i] = n + 1;
- rmost[i] = -1;
- }
- s[0] = 0;
- lmost[0] = rmost[0] = 0;
- for(int i = 1;i <= n;i++)
- {
- //一边计算前缀和
- //一边更新余数的最左位置和最右位置
- s[i] = (s[i-1] + a[i]) % k;
- if(lmost[s[i]] > i)
- lmost[s[i]] = i;
- if(rmost[s[i]] < i)
- rmost[s[i]] = i;
- }
- int ans = 0;
- //根据每个余数出现的次数用组合数求答案
- //前缀和都余i的对应的区间长度
- for(int i = 0;i < k;i++)
- ans = rmost[i] - lmost[i];
- cout << ans;
- return 0;
- }
我们用 lmost 和 rmost 保存第一个前缀和余数最左和最右的下标。整个程序复杂度也是 $O (n+k)$