高维前缀和乱讲

1.4k 词

OI-Wiki 看不懂啊，学了一上午。

常见的二维前缀和求法多为容斥原理，虽然这样的计算相对直观且便于记忆，但是当维数往上升高时其复杂度会大大提高，对于更高维度的前缀和可以使用 “高维前缀和” 这一方法，本质上是基于 DP 的。

首先我们可以了解一种一般的优化，我们先对每一 “行” 求前缀和，再累积他们的前缀和；然后对每一 “列” 求前缀和，再累积他们的前缀和……其实就是对于 每个维度分别求和。

显然对于 t≤3t \leq 3 这样子的优化是不明显的，但是在 OI 中，如果我们把 nn 位二进制数看成一个有着 nn 维度的坐标，比如 (111001)2(111001)_2 看作 s1,0,1,0,1s_{1, 0, 1, 0, 1}，此时这种优化的优势就非常明显了。

高维前缀和一般可以解决这种问题

对于所有的 ii，0≤i≤2n−10 \leq i \leq 2^{n} - 1，求 ∑j⊂iaj(⊂ means subset)\sum_{j \subset i} a_j(\subset\text{ means subset})

考虑直接以朴素的复杂度子集枚举做。

对于子集枚举我们有着大家都知道的 O(3n)O(3^n) 的做法：

常见的枚举子集代码是这样的：

for (int s = u; s; s = (s - 1) & u) {
	// s is a subset of u (not empty)
}

单次地枚举子集 SS 的复杂度显然是 2∣S∣2^{|S|} 的。

那么每次大小为 nn 的子集的复杂度就是

O(∑S∈U2∣T∣)O \left(\sum_{S \in U} 2^{|T|} \right)

SS 中大小为 zz 的子集个数是 CznC_z^n 的，然后考虑枚举 zz，改写复杂度式子：

O(∑i=1n(ni)2i)O \left(\sum_{i = 1}^n \binom{n}{i}2^i \right)

二项式定理化简：

∑i=1n(ni)2i=∑i=1n(ni)2i1n−i=(1+2)n−1\sum_{i = 1}^n \binom{n}{i} 2^i = \sum_{i = 1}^n \binom{n}{i} 2^i 1^{n - i} = (1 + 2)^n - 1

那么整个的复杂度就是 O(3n)O(3^n) 的。■\blacksquare

回到正题，施展高维前缀和，复杂度降到 O(n⋅2n)O(n \cdot 2^n)，代码如下：

for (int j = 0; j < n; j++)
	for (int i = 0; i < (1 << n); i++)
		if (i >> j & 1)
			f[i] += f[i ^ (1 << j)]

我们可以这么理解：

本质上和 for 去跑一维维统计是一样的，具体地讲，我们是正序枚举的，所以 i⊕(1<<j)i \oplus (1 << j) 在当前层，而 ii 还在上一层，然后将两者进行合并不就是上述当前层的前缀和吗？

Bonus(口胡): 对于高维差分，只需要把加号变成减号；对于高维后缀和，求法相同，把所有东西取补集。

似乎这个东西也叫做 SOS DP(Sum Over Subset Dynamic Programming)

留言