预处理

预处理

预处理，即在正式处理数据之前的操作，通常目的是优化时间、空间复杂度。

前置知识：

• C++基础语法

本节目录：

• 前缀和与差分

• 二维前缀和与二维差分

• 离散化

• 总结

前缀和与差分

前缀和

我们先看例题：洛谷B3612 求区间和

简而言之，给你一个长度为$n$的正整数数组 $a_1​,a_2​,⋯,a_n​$，有$m$次询问，每次询问给出一对区间$[ l_i, r_i ]$，分别求这 $m$ 个区间的区间和。

如果你不会前缀和算法，你可能会这样写……

#include <bits/stdc++.h>
using namespace std;

int arr[100005]; // 正整数数组
int main() {
    int n; cin >> n; // 输入n
    
    for(int i = 1; i <= n; ++ i) cin >> arr[i]; // 输入数据
    
    int m; cin >> m; // 输入 m
    int l, r;
    
    for(int i = 1; i <= m; ++ i) {
        int ans = 0; // 存结果
        cin >> l >> r; // 输入l, r
        for(int j = l; j <= r; ++ j) // 从l到r累加数组数据
            ans += arr[j];
        cout << ans << endl; // 输出ans
    }
    return 0;
}

但是一提交，结果却……

TLE。 。 。
为什么会超时呢？我们研究一下时间复杂度。

按照最坏情况，$n = 10^5$，区间可能的最大范围是整个数组，也就是$[0, 10^5]$，内外层循环都是$n$次，所以$O(n^2)$的复杂度，循环次数为$10^{10}$，题目时间限制为$1s$，肯定会超时（只要出题人想卡你，显然这道题卡了）。（具体时间复杂度计算和运行时间，看我这篇博客：pass）

我们想一想，如果询问次数过多，可能会有重叠的区间被重复计算，也就造成，同一段数，不断被求和，导致性能的浪费。有没有一种方法，可以使每一个数只被计算一次，之后只需直接使用即可呢？

有的，那就是前缀和！

如果我们开辟一个额外的数组，前缀和数组（prefix，当然你取什么变量都行，只是为了显而易见得知道这个数组的作用），用来存储，原数组前$i$项的和，就是:

$$prefix[k] = \sum_{i=1}^k arr[i], (k = 1,2,...,n)$$

说人话就是：

$$prefix[k] = arr[1] + arr[2] + ... + arr[k], (k = 1,2,...,n)$$

如果原数组$arr = [1, 2, 3, 4, 5]$
则：
$prefix[0] = 0$
$prefix[1] = arr[1] = 1$
$prefix[2] = arr[1] + arr[2] = 3$
$prefix[3] = arr[1] + arr[2] + arr[3] = 6$
$prefix[4] = arr[1] + arr[2] + arr[3] + arr[4] = 10$
$prefix[5] = arr[1] + arr[2] + arr[3] + arr[4] + arr[5]= 15$

观察可以得到：
$prefix[1] = prefix[0] + arr[1]$
$prefix[2] = prefix[1] + arr[2]$
$prefix[3] = prefix[2] + arr[3]$
$prefix[4] = prefix[3] + arr[4]$
$prefix[5] = prefix[4] + arr[5]$

预处理每项$prefix$：
对于每个$prefix[k]$，有递推式：

$$\boxed{prefix[k] = prefix[k - 1] + arr[k], (k = 1,2,...,n)}$$

注意到(注意力惊人)，对于任意的$[l, r]$区间和$ans$就是：

$$\boxed{ans = \sum_{i=l}^r arr[i] = prefix[r] - prefix[l - 1]}$$

有了这两个式子，代码就很好写了：

#include <bits/stdc++.h>
using  namespace  std;

int arr[100005]; // 数组
int prefix[100005]; // 前缀和数组
int main() {
    int n; cin >> n;  // 输入n
    
    for(int i = 1; i <= n; ++ i) { // 因为后面要i-1，所以从1开始，避免数组越界
        cin >> arr[i]; // 输入数据
        prefix[i] = prefix[i - 1] + arr[i]; // 预处理前缀和数组
    }

    int m; cin >> m;  // 输入 m
    int l, r;         
    for(int i = 1; i <= m; ++ i) {
        cin >> l >> r; // 输入l, r
        cout << prefix[r] - prefix[l - 1] << endl; // 直接计算得出答案
    }
    return 0;
}

然后就愉快的AC啦！

时间复杂度$O(n)$（没有循环嵌套），空间复杂度也是$O(n)$.
因为$arr$数组之后不会再用到，所以可以再优化空间：

#include <bits/stdc++.h>
using  namespace  std;

// int arr[100005]; 直接不需要原数组
int prefix[100005]; // 前缀和数组
int main() {
    int n; cin >> n;  // 输入n
    int num; // 临时变量num
    for(int i = 1; i <= n; ++ i) {
        cin >> num;
        prefix[i] = prefix[i - 1] + num; //预处理前缀和数组
    }

    int m; cin >> m;  // 输入 m
    int l, r;         
    for(int i = 1; i <= m; ++ i) {
        cin >> l >> r; // 输入l, r
        cout << prefix[r] - prefix[l - 1] << endl; // 直接计算得出答案
    }
    return 0;
}

以上，我们称$prefix$数组为前缀和数组，求取$prefix$数组的过程为前缀和算法。

前缀和算法可以简化频繁的区间求和操作，但局限是只能离线操作，就是说，如果涉及对数组的值进行更改的操作，就无法使用前缀和。

差分

还是先看例题：洛谷P2367 语文成绩

简而言之：给你一个长度为 $n$ 的数组，给定 $p$ 次操作，每次操作给你三个数 $x, y, z$ ，意为：给第 $x$ 个数到第 $y$ 个数每个数增加 $z$ 。最后输出操作完数组中的最小值。

若初始数组为 nums = [1, 1, 1, 1, 1]
一次为操作：1 2 1
结果为： nums = [2, 2, 1, 1, 1]
第二次操作为：2 4 2
结果为： nums = [2, 4, 3, 3, 1]

如果你还是只会暴力。。

不用想一定会超时，因为 $n <= 5e6$，纯暴力时间复杂度为$O(n^2)$， 明显超出了$1e9$。
如果你不信邪，可以暴力尝试一下：）

这题我们需要使用差分。

我们使用一个数组记录数据之间的差值，这个数组我们称为$diff$数组，和前缀和数组一样，也需要我们预处理出来。

对于数组$nums$：

$$diff[i] = nums[i] - nums[i - 1]$$

我们发现，对于$diff$数组做一次前缀和，可以得到原数组。

$$nums[i] = \sum_{j = 1}^i diff[j]$$

这个证明可以自行百度。

差分是前缀和的逆运算，反之亦然

对于差分数组，有一个很好的性质：
假如要对原数组区间 $[l, r]$ 都加上 $z$，只需在$diff[l]$加上$z$，$diff[r + 1]$ 减去 $z$。

即：
diff[l] += z
diff[r + 1] -= z

因为diff数组是数据之间的差，对于一个区间加上一个数，这个区间之间的数的差值不会改变，因为都变化了，只有端点处有改变，所以只需改变端点处的值即可。

我们对$diff$数组不断进行此操作，最后，通过一次前缀和操作，得到原数组，顺便找到最小值，代码如下：

#include <bits/stdc++.h>
using namespace std;

int diff[5000005]; // 差分数组
int nums[5000005]; // 原数组
int main() {
    int n, p; cin >> n >> p;
    for(int i = 1; i <= n; ++ i) {
        cin >> nums[i]; // 输入原数组
    }

    for(int i = 1; i <= n; ++ i) {
        diff[i] = nums[i] - nums[i - 1]; // 计算差分数组
    }

    while(p --) { // p 次查询
        int x, y, z;
        cin >> x >> y >> z;

        diff[x] += z; // 计算累加
        diff[y + 1] -= z; 
    }

    int ans = INT_MAX; // int的最大值，用于找到最小值
    int num = 0;
    for(int i = 1; i <= n; ++ i) {
        num += diff[i]; // 前缀和操作
        ans = min(ans, num); // 顺便找到最小值
    }
    cout << ans << "\n";
    return 0;   
}

然后就AC啦！

二维前缀和与二维差分

二维前缀和

先看例题：P2004 领地选择

简单来说：给定一个 $N \times M$ 的数字地图，选择一个 $C \times C$ 的一个小正方形，要使得这个正方形内的数之和最大，输出这个正方形左上角的坐标。

这是一个二维前缀和的模板题。
我们需要先求出对于坐标原点的所有矩形之中的数之和。

我们创建一个二维$prefix$数组，用于存取每个点到原点之间的矩形的数字和。

例如坐标 $(a, b)$ 存取的数字为如图区域的和。

如果对于原数组为：

$prefix$数组为：

不难发现，由于容斥原理，每一项 $prefix[i][j]$ 的值为：

$$prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + nums[i][j]$$

每一项的值为，它左边的值：

加上它上面的值：

减去左上重复加过的一个：

再加上本身：

所以对于$(C, C)$开始，每个$C \times C$ 等于：

$$ans = prefix[i][j] - prefix[i - C][j] - prefix[i][j - C] + prefix[i - C][j - C]$$

同理：当前区域减去左边减去右边，加上右上角多减去的一次。

AC Code:

#include <bits/stdc++.h>
using namespace std;
using ll = long long; // long long的简写

ll prefix[1005][1005]; // 差分数组，可能会爆int，需要long long
int main() {
    int N, M, C;
    cin >> N >> M >> C;
    int num = 0;

    for(int i = 1; i <= N; ++ i) {
        for(int j = 1; j <= M; ++ j) {
            cin >> num;
            prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1]  - prefix[i - 1][j - 1] + num; 
            // 处理二维前缀和
        }
    }

    ll ans = 0; // 同样可能爆int
    int x = 0, y = 0;
    for(int i = C; i <= N; ++ i) {
        for(int j = C; j <= M; ++ j) {
            ll res = prefix[i][j] - prefix[i - C][j] - prefix[i][j - C] + prefix[i - C][j - C];
            if(res > ans) {
                ans = res; // 计算最大值
                x = i - C + 1; // 记录坐标
                y = j - C + 1;
            }
        }
    }
    cout << x << " " << y << "\n"; // 输出坐标

    return 0;   
}

二维差分

例题：洛谷P3397 地毯

在 $n \times n$ 的格子上有 $m$ 个地毯，给你 $m$ 次操作，每次操作给你四个数 $x_1, y_1, x_2, y_2$，表示在左上角 $(x_1, y_1)$ 到右下角 $(x_2, y_2)$ 的区域上铺一个地毯。输出 $n$ 行，每行 $n $ 个正整数。第 $i$ 行第 $j$ 列的正整数表示 $(i,j)$ 这个格子被多少个地毯覆盖。

我们直接对原数组二维差分：

$$diff[i][j] = nums[i][j] - nums[i - 1][j] - nums[i][j - 1] + nums[i - 1][j - 1]$$

由于此题特殊，初始数组全都为 $0$，所以我们可以不需要进行二维差分，直接在原数组上操作即可。

对于每次操作，我们只需要在差分数组上进行如下操作：

diff[x1][y1] ++;
diff[x2 + 1][y2 + 1] ++;
diff[x1][y2 + 1] --;
diff[x2 + 1][y1] --;

AC Code:

#include <bits/stdc++.h>
using namespace std;
using ll = long long; // long long的简写
int nums[1005][1005]; // 原数组

int main() {
    int n, m;
    cin >> n >> m;
    while(m --) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        nums[x1][y1] ++; // 直接在原数组上操作
        nums[x2 + 1][y2 + 1] ++;
        nums[x1][y2 + 1] --;
        nums[x2 + 1][y1] --;
    }

    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= n; ++ j) {
            nums[i][j] += nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1]; // 二维前缀和
            cout << nums[i][j] << " "; // 输出
        }
        cout << "\n";
    }
    return 0;
}

离散化

离散化是将一个连续的数列映射到一个离散的数列上，通常用于处理区间问题。
离散化的思路是：将原数组中的数进行排序，去重，得到一个新的数组，然后用原数组中的数去映射新的数组，得到一个新的离散化后的数组。

离散化的步骤：

1. 将原数组中的数进行排序，去重，得到一个新的数组。
2. 用原数组中的数去映射新的数组，得到一个新的离散化后的数组。
3. 对新的离散化后的数组进行处理，得到结果。
4. 输出结果。

#include <bits/stdc++.h>
using namespace std;
using ll = long long; // long long的简写
int arr[100005]; // 原数组
int arr2[100005]; // 离散化后的数组
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++ i) {
        cin >> arr[i]; // 输入原数组
        arr2[i] = arr[i]; // 离散化后的数组
    }

    sort(arr2 + 1, arr2 + n + 1); // 排序
    int len = unique(arr2 + 1, arr2 + n + 1) - arr2 - 1; // 去重

    for(int i = 1; i <= n; ++ i) {
        arr3[i] = lower_bound(arr2 + 1, arr2 + len + 1, arr[i]) - arr2; // 映射
        cout << arr3[i] << " "; // 输出离散化后的数组
    }
    cout << "\n";
    return 0;
}

离散化的时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n)$。

总结

预处理算法是一个非常重要的算法思想，能够有效地提高程序的运行效率。前缀和和差分是最常用的预处理算法，能够快速地计算区间和。二维前缀和和二维差分则是对前缀和和差分的扩展，能够处理二维数组的问题。离散化则是将连续的数列映射到离散的数列上，能够有效地处理区间问题。

预处理算法的应用非常广泛，尤其是在ACM竞赛中，掌握预处理算法的思想和技巧，对于提高解题效率和能力有很大的帮助。

完结撒花！！！