16.前缀和、差分

发表于 更新于 分类于 ，

前缀和、差分

前缀和与差分作为互补技术，分别通过预处理和逆运算高效处理数组的区间查询与批量修改问题。

前缀和

例：区间和

给定 \(n\) 个正整数组成的数列 \(a_1,a_2,\cdots,a_n\) 和 \(m\) 个区间 \([l_i,r_i]\)，分别求这 \(m\) 个区间的区间和。

对于所有测试数据，\(n,m\leq 10^5\)，\(a_i\leq 10^4\)

这个问题涉及多次询问，每次都加一遍效率很低。

前缀和是一种简单而强大的预处理技术。它通过预先计算数组中从第一个元素到每个位置的元素之和，使得我们能够在O(1)的时间内求出任意区间的和。

对于一个数组 \(a_1,a_2,\cdots,a_n\)，我们定义前缀和数组 \(s_i\) 为:

\(s_i = \sum_{j=1}^i a_j\)

也就是说：

  • \(s_1 = a_1\)
  • \(s_2 = a_1 + a_2\)
  • \(s_3 = a_1 + a_2 + a_3\)
  • ...以此类推

有了前缀和数组后，要求区间 \([l,r]\) 的和，只需要用 \(s_r - s_{l-1}\) 即可。这是因为:

  • \(s_r\) 包含了 \(a_1\) 到 \(a_r\) 的所有元素之和
  • \(s_{l-1}\) 包含了 \(a_1\) 到 \(a_{l-1}\) 的所有元素之和
  • 两者相减就得到了 \(a_l\) 到 \(a_r\) 的和

这样，我们只需要O(n)的时间预处理出前缀和数组，就可以在O(1)的时间内回答任意区间和的询问。对于有大量询问的情况，这种方法比每次都重新计算区间和要高效得多。

例如对于数组 [1,2,3,4,5]:

  • 前缀和数组为 [1,3,6,10,15]
  • 要求区间[2,4]的和，只需计算 s[4] - s[1] = 10 - 1 = 9

用递推的方式\(O(n)\)就可以得到一个数组的前缀和数组，设数组为a[maxn]，前缀和数组为pre[maxn]

1
2
3
4
pre[0] = 0;  // 假设数组数据从下标 1 开始，用 0 作为“哨兵”
for(int i = 1; i <= n; i ++) {
    pre[i] = pre[i - 1] + a[i];  // 递推计算前缀和
}

对任意\([i,j]\)（闭区间为例）区间和，pre[j] - pre[i - 1] 可以得到

例：最大加权矩形

给定一个 \(n\times n\) 的矩阵，矩阵中的每个元素都是整数，范围在 \([−127,127]\) 之间。求矩阵中所有可能的矩形中，元素和最大的那个矩形的和。

例如对于矩阵： 

1
2
3
4
 0 –2 –7  0 
 9  2 –6  2
-4  1 –4  1 
-1  8  0 –2

左下角的 \(3\times 2\) 矩形：

1
2
3
9  2
-4  1
-1  8

和为 15。

先考虑最直观的思路，枚举所有矩形的“左上点”和“右下点”，就算提前计算了所有点的“左上方”的和，至少也是 \(O(n^4)\) 的复杂度了。

在复杂度理论中已了解过最大连续和的\(O(n)\)解法，假设最大矩形是 左上点\((r_{1},c_{1})\)，右下点 \((r_{2},c_{2})\)之间的矩形，如果把矩阵其它行都去掉，只保留\([r_{1},r_{2}]\) 这些行，把每一列的和看作一个整体，就能得到一个 \(n\) 元素序列，这个序列的最大连续和，就是\((r_{1},c_{1}), (r_{2},c_{2})\)这个矩形的和。

1
2
3
4
5
6
..........
..........
##@@@@#### ┐
##@@@@####  > 这些行的每一列的和看作一个元素（一列#相加），求最大连续和（@那些列）
##@@@@#### ┘
..........

对于任意行起点\(r_{1}\)、行终点\(r_{2}\)，只要能快速得到这些行的各列之和，就能\(O(n)\)求它的最大连续和。

预处理每一列的前缀和（\(O(n^2)\)），这一列的任意起点到终点的和就能立刻得到，枚举行起点（\(O(n)\)）和行终点（\(O(n)\)）以及计算这些行的最大连续和（\(O(n)\)），取最大就是最大矩形了，这个方案的复杂度是\(n^2+n^3=O(n^3)\)。

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
#include<cstdio>
#include<algorithm>
const int maxn = 211;
// 预处理每一列的前缀和
int n, a[maxn][maxn];
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < n; j ++) {
            scanf("%d", &a[i][j]);
            a[i][j] += i == 0 ? 0 :a[i - 1][j]; // 原地保存列方向前缀和
        }
    }
    int ans = a[0][0];
    for(int r1 = 0; r1 < n; r1 ++) {
        for(int r2 = r1; r2 < n; r2 ++) {
            int pre = 0;
            for(int i = 0; i < n; i ++) {
                pre += a[r2][i] - (r1 == 0 ? 0 : a[r1 - 1][i]); // 列方向[r1,r2]这一段的和作为一个元素
                ans = std::max(ans, pre);
                if(pre < 0) {
                    pre = 0;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

差分

差分是前缀和的逆运算。对于一个数组 \(a\)，它的差分数组 \(b\) 定义为：

  • \(b_1 = a_1\)
  • \(b_i = a_i - a_{i-1}\) \((i>1)\)

容易发现，原数组的任意一个元素都可以通过差分数组的前缀和还原：

\(a_i = \sum\limits_{j=1}^i b_j\)

差分的一个重要性质是：如果要对原数组的一个区间 \([l,r]\) 同时加上一个数 \(x\)，只需要：

  • 令 \(b_l\) 加上 \(x\)：因为\(a_{l}\)加了\(x\)而\(a_{l-1}\)没加，\(b_{l}=a_{l}-a_{l-1}\)所以加\(x\)；
  • \(b_{l+1}\sim b_{r}\) 不变，因为\(a_{l}\sim a_{r}\) 都加了 \(x\)，它们相邻的差不变；
  • 令 \(b_{r+1}\) 减去 \(x\) （如果 \(r+1\) 存在的话），因为\(a_{r+1}\)没有加\(x\)
  • 后面的不变

也即原数在一个区间同时加一个数，差分数组只需要改变区间首尾两个数。

例：区间变化

给定一个长度为 \(n\) 的数组 \(a\)，有 \(p\) 次操作，每次操作给定三个数 \(x\)、\(y\)、\(z\)，表示将数组 \(a\) 中从第 \(x\) 个到第 \(y\) 个元素（包括这两个位置）都加上 \(z\)。最后求整个数组中的最小值。

模拟这个过程复杂度会很高，如果能把区间修改问题转换为单点修改问题，就会快很多。

参考代码

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
#include<cstdio>
#include<algorithm>
const int maxn = 5e6 + 10;
int n, p, a[maxn], l, r, x;
int main() {
    scanf("%d%d", &n, &p);
    a[0] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = n; i >= 1; i --) {
        // 原地计算差分，for循环逆序是避免要用的值被先覆盖
        a[i] -= a[i - 1];   
    }
    while(p --) {
        scanf("%d%d%d", &l, &r, &x);
        a[l] += x;
        if(r + 1 <= n) {
            a[r + 1] -= x;
        }
    }
    int ans = a[1];
    for(int i = 1; i <= n; i ++) {
        a[i] += a[i - 1];
        ans = std::min(ans, a[i]);
    }
    printf("%d\n", ans);
    
    return 0;
}

例：二维区间修改

给定一个 \(n\times n\) 的网格，有 \(m\) 次操作，每次操作给定四个数，表示将左上角为 \((r_1,c_1)\)，右下角为 \((r_2,c_2)\) 的矩形区域内的每个格子都加 \(1\)。最后输出每个格子被加了多少次。

数据范围 \(n,m \leq 1000\)

根据题目给的数据范围，这道题可以想简单点，对于每个 左上 \((r_1,c_1)\)、右下 \((r_2,c_2)\) 的矩形，都可以看作 \(r_{1}\sim r_{2}\) 这些行分别进行一次区间增长，分别用差分来单点更新：

1
2
3
4
5
6
0  0  0  0  0  0
0 +1  0  0  0 -1
0 +1  0  0  0 -1
0 +1  0  0  0 -1
0 +1  0  0  0 -1
0  0  0  0  0  0

复杂度分析：初始化计算每一行差分数组，\(O(n^2)\)，\(m\) 个操作、每个操作最坏对 \(n\) 行的差分数组做 \(O(1)\) 操作，总复杂度 \(n^{2}+mn=O(mn)\)，\(n,m \leq 1000\)，复杂度可接受。

更多思考：一些同学可能想到两次差分，把多行多次差分数组更新变成首尾两次：

1
2
3
4
5
6
0  0  0  0  0  0
0 +1  0  0  0 -1
0  0  0  0  0  0
0  0  0  0  0  0
0  0  0  0  0  0
0 -1  0  0  0 +1

而这道题\(m\)和\(n\)范围一致，即使把 \(O(mn)\) 优化到 \(O(m)\)，初始差分表也有个 \(O(n^2)\) 在，\(n^{2}+m=O(n^2)\) ，复杂度没有本质提升。不过如果 \(m\) 比 \(n\) 大很多，那么这个优化还是有意义的，可以尝试。