revkiru Blog

高维前缀和乱讲

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

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

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

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

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

对于所有的 $i$,$0 \leq i \leq 2^{n} - 1$,求 $\sum_{j \subset i} a_j(\subset\text{ means subset})$

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

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

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

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

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

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

$$ O \left(\sum_{S \in U} 2^{|T|} \right) $$

$S$ 中大小为 $z$ 的子集个数是 $C_z^n$ 的,然后考虑枚举 $z$,改写复杂度式子:

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

二项式定理化简:

$$ \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(3^n)$ 的。$\blacksquare$

回到正题,施展高维前缀和,复杂度降到 $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 \oplus (1 « j)$ 在当前层,而 $i$ 还在上一层,然后将两者进行合并不就是上述当前层的前缀和吗?

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

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

#OI #DP #算法 #数学