前缀和&差分
前缀和
一维前缀和
输入整数n,q(1<=n,q<=105),和长为n的数组a。
接下来q行，每行输入两个数l,r(1<=l<=r<=n)，要求输出区间[l,r]内所有元素的和，即∑i=lrai。
NOTE · 说明
题目描述一般都是1下标，笔者写代码一般都是0下标，故本文所有题目描述均采用1下标，代码部分均为0下标。0下标指将数组第一个元素放到a[0],1下标指将第一个元素放到a[1],将a[0]空出来
暴力做法就是对于每一个询问，遍历l到r求和，但这样时间复杂度是O(nq),最坏情况下会超时。
这里介绍一下前缀和算法，前缀和是一种常用的算法预处理技巧，通过提前计算数组前若干个元素的累加和，实现快速的区间求和。
注意到
i=l∑rai=i=0∑rai−i=0∑l−1ai。
任意一个区间和，都可以转换为两个前缀和相减。
我们可以先预处理所有的前缀和，进而O(1) 的求出所有区间和，总时间复杂度O(n+q)，空间复杂度O(n)。
定义前缀和数组s,其中s[i]表示前i个元素的和。
初始s[0]=0，递推公式s[i+1]=s[i]+a[i]。
s[0]s[1]s[2]s[n]=0=a[0]=a[0]+a[1]⋮=a[0]+a[1]+⋯+a[n−1]
则有 ∑i=lrai=s[r+1]−s[l]
TIP · 技巧
这里定义s[0]=0，表示前0个数的和为0，避免l=0时需要特判。
例:
a=[1,3,2,5,4]
对应前缀和数组为
s=[0,1,4,6,11,15]
查询区间[1,3]的区间和
a[1]+a[2]+a[3]=3+2+5=10=s[4]−s[1]
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
int n,q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0;i < n;i++) cin >> a[i];
vector<ll> pre(n + 1);
for (int i = 0;i < n;i++) pre[i + 1] = pre[i] + a[i];
while (q--)
{
int l,r;
cin >> l >> r;
l--;r--;
cout << pre[r + 1] - pre[l] << endl;
}
}
|
TIP · 技巧
提示：除了加法以外，还有一些操作也可以运用这种前缀思想，例如前缀异或和等
课后练习
二维前缀和
输入n,m,q(1<=n,m,q<=105,1<=n∗m<=105)和一个n∗m的矩阵，接下来q行，每行给出一个矩阵的左上角和右下角坐标。
输出q行，每行一个整数，表示这个矩阵的和
暴力做法是遍历每个查询的矩阵，时间复杂度O(nmq)，会超时。
按照之前一维前缀和的思路，这里可以用二维前缀和，具体见下图。时间复杂度O(nm+q)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
int n,m,q;
cin >> n >> m >> q;
vector<vector<int>> a(n,vector<int>(m));
for (int i = 0;i < n;i++)
{
for (int j = 0;j < m;j++)
{
cin >> a[i][j];
}
}
vector<vector<ll>> pre(n + 1,vector<ll>(m + 1));
for (int i = 0;i < n;i++)
{
for (int j = 0;j < m;j++)
{
pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + a[i][j];
}
}
while (q--)
{
int x1,x2,y1,y2;
cin >> x1 >> y1 >> x2 >> y2;
x1--;y1--;x2--;y2--;
ll ans = pre[x2 + 1][y2 + 1] - pre[x2 + 1][y1] - pre[x1][y2 + 1] + pre[x1][y1];
cout << ans << endl;
}
}
|
课后练习
前缀和与哈希表
输入n(1<=n<=105),k(−107<=k<=107)和一个长为n的数组a(−1000<=a[i]<=1000),
输出数组中和为k的子数组个数.
暴力做法是统计所有子数组的和，如果和为k，ans++，最后输出ans，时间复杂度O(n2)。
NOTE · 说明
长为n的数组一共有2n∗(n+1)个非空子数组。
当左端点为1时，右端点可以为1,2,...,n，总共n个子数组
当左端点为2时，右端点可以为2,3,...,n，总共n−1个子数组
当左端点为n时，右端点可以为n，总共1个子数组
故总共有∑i=1ni=2n∗(n+1)个子数组
根据我们刚刚求区间和的思路，我们需要求满足s[r+1]−s[l]==k的不同(l,r)的数量。即求s[r+1]−k==s[l]的(l,r)数量，我们可以创建一个哈希表用来统计数量，接着我们遍历前缀和数组，假设遍历到下标i,记x=s[i],则满足要求的数字为x−k，所有满足s[j]=x−k的下标j都可以与i配对，故答案加上cnt[x−k]，接着cnt[x]++。时间复杂度O(n)
WARNING · 警告
只有位于当前位置之前的前缀和才能与当前前缀和组成合法的非空子数组，因此必须先查询答案，再更新哈希表。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
int n,k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0;i < n;i++) cin >> a[i];
vector<ll> s(n + 1);
for (int i = 0;i < n;i++) s[i + 1] = s[i] + a[i];
ll ans = 0;
unordered_map<ll,ll> cnt;
for (ll x : s)
{
ans += cnt[x - k];
cnt[x]++;
}
cout << ans << endl;
}
|
课后练习
差分
一维差分
输入n,q(1<=n,q<=105)和长为n的数组a(−109<=a[i]<=109)，接下来q行，每行三个整数l,r,x(1<=l<=r<=n,−109<=x<=109)表示将下标在[l,r]的元素加上x。
输出一行n个整数,表示进行所有操作后的数组a。
暴力做法是对于每个询问，遍历数组a的[l,r]，给每个数加上x。时间复杂度O(nq),会超时。
这里引入一个新的概念——差分
对于数组a，相邻元素两两做差，再在前面补上a[0],就得到了差分数组d
例：a=[1,3,3,5,8]，d=[1,2,0,2,3]
差分与前缀和的关系就类似积分与导数的关系，对差分数组求前缀和就能得到原数组。
那么差分数组有什么性质呢？
假设我们将数组a中[1,3]的元素加上3，得到新数组a′=[1,6,6,8,8],新差分数组d′=[1,5,0,2,0]
再将数组a′中[2,4]的元素加上5，得到新数组a′′=[1,6,11,13,13],新差分数组d′′=[1,5,5,2,0]
注意到，改变原数组[1,3]时，差分数组d[1]加了3，d[2],d[3]没变，d[4]减了3。
改变原数组[2,4]时，差分数组d[2]加了5，d[3],d[4]没变。
由此我们可以得出，对于原数组[l,r]加上x时，对应的差分数组d[l]+=x,d[r+1]−=x。
因此对于这道题，我们可以先求出原数组a的差分数组，再在差分数组上进行这些操作，最后再对差分数组求前缀和从而得到新数组。时间复杂度O(n+q)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
int n,q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0;i < n;i++) cin >> a[i];
vector<ll> d(n + 1);
d[0] = a[0];
for (int i = 1;i < n;i++) d[i] = a[i] - a[i - 1];
while (q--)
{
int l,r,x;
cin >> l >> r >> x;
l--;r--;
d[l] += x;
d[r + 1] -= x;
}
ll ans = 0;
for (int i = 0;i < n;i++)
{
ans += d[i];
cout << ans << " ";
}
cout << endl;
}
|
课后练习
