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(\sum_{S \in U} 2^{|T|}) \]\(S\) 中大小为 \(z\) 的子集个数是 \(C_z^n\) 的，然后考虑枚举 \(z\)，改写复杂度式子：
\[O(\sum_{i = 1}^n \binom{n}{i}2^i) \]二项式定理化简：
\[\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)
标签：乱讲,前缀,复杂度,枚举,子集,sum,高维 From： https://www.cnblogs.com/Yuics/p/18327946