跳转至

0x05 前缀和与差分数组

[toc]

1. 前缀和

1.1. 一维前缀和

对于一个给定的数列A，它的前缀和S[i] = A[0] + A[1] + ... + A[i]。也可以通过递推式表示S[i] = S[i - 1] + A[i]。

我们可以表示数列A的某个下标区间内的和，通过前缀和相减的形式。

1
2
3
sum(l, r) = a[l] + a[l + 1] + ... + a[r]
S[r] - S[l - 1] = a[l] + a[l + 1] + ... + a[r]
sum(l, r) = S[r] - S[l - 1]

这样当我们需要频繁的求数列A内一段连续区间的值时，就可以通过O(1)的时间复杂度，而不是O(n)。在构建前缀和数组时需要O(n)的时间复杂度，因此当涉及频繁的查询时前缀和的优势就显现出来了。

假设要查询的次数为m次，那么查询这个操作的时间复杂度上界就是O(n)，总共的时间复杂度就是O(n * m)。如果使用前缀和数组进行简化，时间复杂度就是O(n + m)。

1.2. 二维前缀和

二维的前缀和与一维的类似。S[i][j] =∑∑a[0~i][0~j]，也可以用递推式表示S[i][j] = S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1] + A[i].

我们也同样可以用前缀和的形式表示二维数组中任意一个矩形的值的和。

1
2
sum(x1, y1, x2, y2) = ∑∑A[x1~x2][y1~y2]
sum(x1, y1, x2, y2) = S[x2][y2] - S[x2][y1 - 1] - S[x1 - 1][y2] + S[x1 - 1][y1 - 1]

1.3. 边界情况

对于一维前缀和，可以发现，在求区间的和时，通过前缀和相减的公式会遇到边界问题。

sum(l, r) = S[r] - S[l - 1]当l = 0时，会遇到数组下标为-1的情况。实际上这种情况不需要减去任何前缀和，因为l = 0已经是最开始的元素。但是为了公式的统一计算，我们可以让数组下标从1开始计数，让S[0] = 0。这样就没有边界情况，对于任何的区间都可以统一地使用这个公式计算。

对于二维前缀和，可以从一维前缀和推理出，会遇到同样的边界情况，这时同理让S[0][y] = S[x][0] = 0即可。

2. 差分

2.1. 一维差分

差分与前缀和是一堆逆运算，对于数列A，它的前缀和为S，那么数列S的差分数列D就是A。

首先对于数列A的一维差分数组D的定义为D[i] = A[i] - A[i - 1]，而对于前缀和A[i] = S[i] - S[i - 1]。

差分适合需要频繁整体改变数列的某一连续自区间的值，本来需要O(n)的复杂度的运算通过差分可以降到O(1)。

差分实际上只需要插入运算，不需要考虑开始的构造。因为可以把差分的构造过程转化为n次插入过程。如A[i] = m，实际上是对A[m, m]这一区间插入m的值。

那么一维差分的插入运算为

1
2
3
4
insert(left, right, c) {
    d[left] += c;
    d[right + 1] -= c;
}

2.2. 二维差分

同样的，对于二维差分，我们也只需要想出插入这个操作。但是因为差分过于抽象，所以我们从前缀和的角度去思考。插入这个操作的参数为insert(x1, y1, x2, y2, c)，即为一个子矩阵，对这个子矩阵的操作的结果就是让原数组（前缀和数组）的值都增加c。那么我们就可以思考一下，对差分矩阵的操作会怎样影响前缀和数组，如果我们让x1, y1让一点加c，那么对于任意的S[x][y]，x>=x1 && y>=y1的值都会加c，而对于任意的S[x][y]，x>x2 && y>y2都被无辜的影响了，因此我们要再减去它们，最终把多减去的重合部分加上，就完成了插入操作。

1
2
3
4
5
6
insert(x1, y1, x2, y2, c) {
    d[x1][y1] += c;
    d[x1][y2 + 1] -= c;
    d[x2 + 1][y1] -= c;
    d[x2 + 1][y2 + 1] += c;
}

2.3. 边界问题

与前缀和类似，差分的边界在于d[n]，我们可以给数组多开点空间，然后赋值为0。

最后更新: May 29, 2022