前缀和问题再探究

普通的前缀和

一种用于解决仅有询问的区间和查询问题的数据结构。

形如：给定一个数列， 个询问，每次询问给出 ，求区间和。

通过在线性时间内预处理出从 到 的和，可以在 时间通过 得到 的值。

前缀和不仅可以存储“和”的形式，还可以存储一切具有可加性的东西。比如最值，但需要注意的是，如果存储的东西不具有可减性，那么就不能通过 来计算区间的最值。

至于为什么要提这个，在高维前缀和中，我们可能不需要维护减操作，这类仅具有可加性的操作就有意义了。

高维前缀和

二维前缀和

一般来说，我们求二维前缀和会使用容斥原理。

设

那么有递推式：

同样的，如果我们想求出某一个矩阵的和，比如 到 的和，即

也可以使用容斥原理，答案为：

注意到，虽然看上去二维前缀和只是带了一个 的常数，但是再高维，用到 元容斥的复杂度是 的，总复杂度就是 ，在有些情况下会大大的爆炸，所以我们就有了另外一种求高维前缀和的方法。

就是 DP。

我们对于每一个维度分别进行递推，还是以二维为例，我们先对第一维进行 DP，相当于做一次一维前缀和：

初始每一个 。

此时有

这时我们再对第二维做一次 DP：

注意到， 现在是完整的，即

和原来的 相加，得到完整的 ，非常巧妙。

n 维前缀和

其实有了上面的铺垫， 维前缀和也就迎刃而解了。

我们分别对每一维做一次 DP，每一次 DP 枚举整个高维空间的点，时间复杂度为 。

至于正确性，可以和 时一样讨论。

维前缀和一般不会用来求什么最大子超立方体之类的东西，一般就是一个转化，然后求每一个数的答案。

但是的话，维数高了数组会显得很乏力，我们需要一种特殊的形式，比如用状压。

常见的高维前缀和技巧有按二进制位状压，按质因数分解状压等。

时间复杂度一般可以把暴力的一个 变成 。