高维前缀和乱讲
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)