算法之前缀和（一）

本文为手工编写，非AI生成，请放心食用

什么是前缀和

• 前缀和（Prefix Sum）是一个在算法和数据结构中非常基础且重要的预处理技巧
• 它通过预处理一段数据的 前缀 信息，高效且简单的维护 可差分 并且具有 结合律 数据类型的区间信息

*什么是可差分? 可差分就是这种数据类型所求的运算是可逆的
例如加法就是典型的可差分运算，因为可以通过减法还原成原来的数据 ，而 max 运算就是典型的不可差分运算，因为知道 max(a,b)=c 无法仅通过 c 和 a 准确还原出 b。

*要是结合律都不知道重读小学二年级吧

举个例子

接下来我们将以 求和 为基础运算，来为前缀和做一个具体的介绍

典型例题

给定一个 n 个数的整数序列 a，有 q 次询问，每次询问输出区间 $[l,r]$ 的和

暴力思想：对于每次询问，遍历区间 $[l,r]$ 中的每一个数，累加输出即可。

对于暴力思想，时间复杂度是 O(q⋅n)，由于在每次询问过程中，我们重复遍历了很多次相同元素，这显然是不必要的，应该存在更优的解法

考虑优化

假设有这样一组数据：
n=5,q=3

第一次询问 $[2,4]$

第二次询问 $[2,5]$

第三次询问 $[1,4]$

统计一下每个数分别被加了多少次

我们惊奇的发现 $[2,4]$ 竟然被统计了 $3$ 次！

于是考虑存储某些区间的和，以加速这个询问的计算

该怎么存储区间呢，存储哪些区间呢？

这就涉及到了前缀和的核心思想 拆区间为前缀区间的组合

什么是前缀区间呢？就是指左端点下标为 $1$ 的区间

考虑区间 $[l,r]$ 的和：

\[ \sum_{i=l}^{r}a_i = a_l + a_{l+1} + a_{l+2} + ... + a_r \]

我们可以把它拆成两个前缀区间的差

\[ \sum_{i=l}^{r}a_i = \sum_{i=1}^{r}a_i - \sum_{i=1}^{l-1}a_i = a_1 + a_2 + ... + a_r - (a_1 + a_2 + ... + a_{l-1}) \]

形象的说：

定义

\[ sum(l,r) = \sum_{i=l}^ra_i \]

所求的区间和 $sum(l, r)$（蓝色）就等于 $sum(1, r) - sum(1, l-1)$ (红色 - 绿色)

Amazing啊! (毕导音)

我们通过前缀数组可以组合出任意区间！

只要计算出前缀数组，任意区间的和都可以在 $O(1)$ 时间内通过前缀和公式计算出来

前缀数组预处理

那么怎么计算前缀数组呢？

其实十分巧妙

我们列出前缀数组的表达式

\[ sum(1,1) = a_1 \] \[ sum(1,2) = a_1 + a_2 \] \[ sum(1,3) = a_1 + a_2 + a_3 \] \[ sum(1,4) = a_1 + a_2 + a_3 + a_4 \]

我们再次发现进行了很多不必要的计算

观察式子我们就会发现:
可以用 $sum(1, 1)$ 替换 $sum(1,2)$ 中的 $a_1$

可以用 $sum(1, 2)$ 替换 $sum(1,3)$ 中的 $a_1 + a_2$

可以用 $sum(1, 3)$ 替换 $sum(1,4)$ 中的 $a_1 + a_2 + a_3$

找规律可以发现

\[ sum(1, i) = sum(1, i-1) + a_i \]

这个递推公式显然可以通过遍历 $i$ 从 $1$ 到 $n$ 进行快速计算

vector<int> sum(n+1, 0); /* sum[i]表示上文中的sum(1,i) */

for(int i = 1;i <= n;i++){
    sum[i] = sum[i-1] + a[i];
}

正确性证明：由于 $i$ 是顺序遍历的，遍历到 $i$ 时下标比 $i$ 小的 sum 显然都已经计算完毕，综上所述，此计算方法正确

Amazing啊! $\times 2$

我们通过 $O(n)$ 递推预处理高效的算出了每个前缀和数组的信息

在询问时可以直接在线 $O(1)$ 回答

while(q--){
    int l, r;
    cin >> l >> r;
    cout << sum[r] - sum[l-1] << "\n";
}

如此以来，我们成功的将 暴力的区间循环 转换为了 精妙的数组构造，通过预处理将总时间复杂度降到了 $O(n+q)$

其他应用

前缀和不止能用于区间求和，还可以求 - 区间异或和 - 区间乘积与字符串哈希 - 二维前缀和 - 余数前缀和

预知后事如何，且听下回分解!