前缀和

前置问题

在认识前缀和之前, 首先提出万恶的需求: 对于一个数组, 并给出 q 次询问, 每一次都询问这个数组在 [l, r] 范围内的和

我们最开始的思路是, 每一次询问, 都去遍历一遍 [l, r] 区间去进行求和, 得到如下代码.

int sum = 0;
while (q--)
	for (int i = l; i <= r; i++)
		sum += arry[i];

Easy! 当我们以为问题解决的时候, 问题升级了, 希望你在 **1s 内求出答案, 并且 ${n * q}$ 的值处于 10^6^ ** , 再去使用上面的方法, 就会喜提 TLE , 这时我们认识到, 每一个询问都进行区间求和的时间复杂度是 $O(nq)$ 的, 纯粹的暴力在升级的问题中是不可行的.

思考优化

我们进一步思考, 突然发现一个有趣的性质, 如果要去求出区间 [l, r] 内的和, 只需要使用 sum([1, R]) - sum([1, L - 1]) (Ⅰ)就可以轻松得到, 而不再需要去进行遍历, 最重要的是我们只需要对整个数组求一次和, 即利用 sum([1, x]) = sum([1, x - 1]) + arry[x](Ⅱ) 即可, 这样每一次询问, 我们只需要去利用式子 (Ⅰ)

进行 $O(1)$ 的运算就可以了, 那么总共我们只需要花费 $O(n + q)$ 的时间复杂度就完美的实现了对升级问题的优化.

前缀和

通过对问题的思考优化, 这时候我们引出前缀和的概念, 相信你就应该可以理解了.

**前缀和指一个数组的某下标之前的所有数组元素的和 ( 包含其自身 ) **

比如我们有一个数组 [1, 2, 3, 4, 5], 那么其对应的前缀和数组就是 [1, 3, 6, 10, 15]

用表达式来表示的话就是 sum([1, x]) = sum([1, x - 1]) + arry[x] 当 x == 1 时 sum([1, x]) = arry[x]

代码实现则是:

int sum[N], arry[N];
for (int i = 1; i<= N; i++) 
    sum[i] = sum[i - 1] + arry[i];
while (q--)
    cout << sum[r] - sum[l - 1] << endl;

一维前缀和的总结

那么对于前缀和只能解决加法问题吗? 当然不是, 它还可以解决像区间异或的情况, 也即 xor(l, r) = xor([1, R]) ^ xor([1, L - 1])

我们可以总结一下, 如果需要求出区间 [l, r] 中元素操作为 x 的结果时, 只要操作 x 满足 X(l, r) = X([1, r]) X X([1, l - 1]) 就可以使用前缀和的思想进行优化

例题

• 洛谷 U69096

• 最大の和

• [USACO05JAN]Moo Volume S

• [USACO16JAN]Subsequences Summing to Sevens S

二维前缀和

对于一维前缀和, 我们已经有一定了解了. 那么我们开始加速.

我们给出一个数字矩阵 $a$, 可以将其视为二维数组

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

现在要求我们去求出任意一个子矩阵的和, 有了一维前缀和的经验, 我们会想到记录任意一个点到 $(1, 1)$ 的矩阵的和, 也即 $sum_{x, y} = \sum_{i = 1} ^ {x} \sum_{y = 1} ^ {y} a_{i, j}$

于是我们可以得到下面的 $sum$

1  3  7  10
6  9  15 22
12 18 29 45

思路是很清晰的, 不过我们下面遇到了两个问题:

1. 递推求 $sum_{i, j}$ 的过程: $sum_{i, j} = sum_{i - 1, j} + sum_{i, j - 1} + a_{i, j}$ 如果不理解可以对着下面这个图理解一下

   

   由于添加了 $sum_{i - 1, j}, sum_{i, j - 1}$ 故对于 $sum_{i - 1, j - 1}$ 重复添加了, 所以需要减去

2. 我们如何通过 $sum$ 矩阵求出 $(x_1, y_1) - (x_2, y_2)$ 子矩阵的和

   

   根据类似的思考, 再根据图看一下, 可以发现答案为 $sum_{x_1, y_1} - sum_{x_1 - 1, y_2} - sum_{x_2, y_1 - 1} + sum_{x_1 - 1, y_1 - 1}$

例题

• 洛谷P1378最大正方形