差分与前缀和

前缀和

作用:求某一段的和 ( [l,r] )

前缀和的思路是这样的,对于一个给定的数组 nums,我们额外开辟一个前缀和数组进行预处理:
Acwing模板

1
2
3
4
5
6
7
8
9
10
a[0]=0
for (int i = 1; i <=n; i++)
scanf("%d",&a[i]);

s[0] = 0;
for (int i = 1; i <=n; i++)
s[i]=s[i-1]+a[i];

//------
ans=s[r]-s[l-1]
1
2
3
4
5
6
int n = nums.length;
// 前缀和数组
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)
preSum[i + 1] = preSum[i] + nums[i];

20210811132123

这个前缀和数组 preSum 的含义也很好理解,preSum[i] 就是 nums[0..i-1] 的和。那么如果我们想求 nums[i..j] 的和,只需要一步操作 preSum[j+1]-preSum[i] 即可,而不需要重新去遍历数组了。

回到这个子数组问题,我们想求有多少个子数组的和为 k,借助前缀和技巧很容易写出一个解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int subarraySum(int[] nums, int k) {
int n = nums.length;
// 构造前缀和
int[] sum = new int[n + 1];
sum[0] = 0;
for (int i = 0; i < n; i++)
sum[i + 1] = sum[i] + nums[i];
int ans = 0;
// 穷举所有子数组
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
// sum of nums[j..i-1]
if (sum[i] - sum[j] == k)
ans++;
return ans;
}

这个解法的时间复杂度 $O(N^2)$ 空间复杂度 $O(N)$ ,并不是最优的解法。不过通过这个解法理解了前缀和数组的工作原理之后,可以使用一些巧妙的办法把时间复杂度进一步降低。

优化

前面的解法有嵌套的 for 循环:

1
2
3
4
5
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (sum[i] - sum[j] == k)
ans++;

第二层 for 循环在干嘛呢?翻译一下就是,在计算,有几个 j 能够使得 sum[i] 和 sum[j] 的差为 k。毎找到一个这样的 j,就把结果加一。

我们可以把 if 语句里的条件判断移项,这样写:

1
2
if (sum[j] == sum[i] - k)
ans++;

优化的思路是:我直接记录下有几个 sum[j]sum[i] - k 相等,直接更新结果,就避免了内层的 for 循环。我们可以用哈希表,在记录前缀和的同时记录该前缀和出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int subarraySum(int[] nums, int k) {
int n = nums.length;
// map:前缀和 -> 该前缀和出现的次数
HashMap<Integer, Integer>
preSum = new HashMap<>();
// base case
preSum.put(0, 1);
int ans = 0, sum0_i = 0;
for (int i = 0; i < n; i++) {
sum0_i += nums[i];
// 这是我们想找的前缀和 nums[0..j]
int sum0_j = sum0_i - k;
// 如果前面有这个前缀和,则直接更新答案
if (preSum.containsKey(sum0_j))
ans += preSum.get(sum0_j);
// 把前缀和 nums[0..i] 加入并记录出现次数
preSum.put(sum0_i,
preSum.getOrDefault(sum0_i, 0) + 1);
}
return ans;
}

比如说下面这个情况,需要前缀和 8 就能找到和为 k 的子数组了,之前的暴力解法需要遍历数组去数有几个 8,而优化解法借助哈希表可以直接得知有几个前缀和为 8。

20210811134248

这样,就把时间复杂度降到了 $O(N)$,是最优解法了。

总结

前缀和不难,却很有用,主要用于处理数组区间的问题。

比如说,让你统计班上同学考试成绩在不同分数段的百分比,也可以利用前缀和技巧:

1
2
3
4
5
6
7
8
9
int[] scores; // 存储着所有同学的分数
// 试卷满分 150 分
int[] count = new int[150 + 1]
// 记录每个分数有几个同学
for (int score : scores)
count[score]++
// 构造前缀和
for (int i = 1; i < count.length; i++)
count[i] = count[i] + count[i-1];

这样,给你任何一个分数段,你都能通过前缀和相减快速计算出这个分数段的人数,百分比也就很容易计算了。

但是,稍微复杂一些的算法问题,不止考察简单的前缀和技巧。比如本文探讨的这道题目,就需要借助前缀和的思路做进一步的优化,借助哈希表去除不必要的嵌套循环。可见对题目的理解和细节的分析能力对于算法的优化是至关重要的。

二维前缀和

二维前缀和就是求一个矩阵中所有数的和

1
2
3
4
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:

S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

20220109194750


子矩阵的和

20210811143617

就如图中

知道了两个点的位置和他们的二维前缀和,

图中红色是左上角的那个点的二维前缀和,

红色+黄色部分是右下角的那个点的二维前缀和,

是不是可以用这个来求出他们之间的矩阵的和呢?

也就是这一部分:

20210811143707

图中黑色的部分就是我们要求的那个矩阵和

看到这里yy一下

是不是可以通过某些奇怪的方法求出黑色部分是多少?

20210811143730

D点表示的二维前缀和值是红色部分+两个黄色部分+黑色部分

A点表示的是红色部分

B点表示的是上面的黄色部分+红色部分

C点表示的是下面的黄色部分+红色部分

这样是不是发现有什么神奇的东西快要出现了

这里面只有D的前缀和里面包括黑色部分

只要减去D里面的哪两个黄色部分和红色部分是不是就剩下了我们要求的黑色部分了?

那怎么减去呢?

可以这样:

D - B - C + A

这就是二维前缀和最重要的部分了

化成二维数组的形式就是这样的

$f[i][j]−f[i−1][j]−f[i][j−1]+f[i−1][j−1]$

二维前缀和怎么求

这个可以类比上面求矩阵的思想

只是这个矩阵的右下角是(i,j),左上角也是(i,j)

就是一个11的矩阵

所以也是很好求的

但是上面是已知D,A,B,C求黑色部分

这里你只知道A,B,C和黑色部分

因为是一个11的矩阵吗

所以黑色部分就只有一个元素也就是(i,j)坐标上的那个元素值

所以就可以个加法变减法,减法变加法一个性质的

通过A,B,C和黑色部分来求出D

所以D就可以等于B+C-A+黑色部分:

上面的黄色部分+红色部分+下面的黄色部分+红色部分-红色部分+黑色部分
=上面的黄色部分+红色部分+下面的黄色部分+黑色部分

刚好等于D

方程式为

$f[i][j]=f[i−1][j]+f[i][j−1]−f[i−1][j−1]+a[i][j]$

模板

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
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int Max = 1003;
int a[Max][Max];
int f[Max][Max];
signed main()
{
freopen("acioi.in","r",stdin);
int n,m,c;
cin >> n >> m >> c;
for(register int i = 1;i <= n;++ i)
for(register int j = 1;j <= m;++ j)
cin >> a[i][j],f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
int k;
cin >> k;
for(register int i = 1;i <= k;++ i)
{
int x1,x2,y1,y2;//x1,y1是左上角的坐标,另一对是右下角的坐标
cin >> x1 >> y1 >> x2 >> y2;
cout << f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1];
}
cout << M << endl;
return 0;
}

差分

差分可以简单的看成序列中每个元素与其前一个元素的差。

原数组 进行差分,得到差分数组 ,差分数组求前缀和,又得到原数组

差分数组改变–再求前缀和,得到改变后的数组

1
2
5,6, 4,8, 7, 6,9
5 1 -2 4 -1 -1 3

一维差分

一个区间[L,R]中所有的数全部加上一个C
让一个序列中某个区间内的所有值均加上或减去一个常数。

假如在 3~8 的区间上加上 5,那我们在差分数组中的 3 位置上加上一个 5 ,再在8+1的位置上减一个5

1
2
3
4
5
//区间[l,r]中的所有值都加上常数c
b[l] += c;
b[r+1] -= c;

//每次求前缀和都会有 b[l]+c,得到A[i]只需要加上1个C

20220109205120


二维差分

给一个子矩阵的所有数都加上一个数C
20210811145147

根据二维前缀和表示的是左上角矩形的和,由于差分只涉及前面相邻的数(由一维可以推出),并且由前面范围的数相加得到这个位置的数。那么类比二维前缀和和一维差分,可以简单推测出二维差分的公式

$p[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$

如何从差分矩阵得到原/改变矩阵呢?可以参考下面公式(二维前缀和)

$f[i][j]=f[i−1][j]+f[i][j−1]−f[i−1][j−1]+p[i][j]$

即可以得到改变后的矩阵

比如,我们有一个矩阵 a,如下所示:

1
2
3
1 2 4 3
5 1 2 4
6 3 5 9

那么对应的二维差分矩阵 p 如下:

1
2
3
1  1  2 -1
4 -5 -1 3
1 1 1 2

应用

如果我们要在左上角是 (x1,y1),右下角是 (x2,y2) 的矩形区间每个值都 +a,如下图所示

20210811150918

在我们要的区间开始位置(x1,y1)处 +c,根据前缀和的性质,那么它影响的就是整个黄色部分,多影响了两个蓝色部分,所以在两个蓝色部分 -c 消除 +c 的影响,而两个蓝色部分重叠的绿色部分多了个 -c 的影响,所以绿色部分 +c 消除影响。所以对应的计算方法如下:

1
2
3
4
diff[x1][y1] += c;
diff[x1][y2+1] -=c;
diff[x2+1][y1] -=c;
diff[x2+1][y2+1] += c;

最后在求前缀和 回去就行

20220109210837