高维前缀和 SOS DP
子集和问题
其实这类算法更多的是解决子集和 （sum of subset） 问题，因此也叫 SOS DP。
$$ sum[i] = \sum_{j \subseteq i} a[j] $$即
$$ sum[i] = \sum_{j | i = i} a[j] $$这里我们有个非常显然的做法是可以枚举所有集合判断是否是当前所求的 $sum[i]$ 的子集并求和的 $O(2^n \times 2^n)$ 的做法。以及一个比较显然的可以通过直接枚举子集的做法：
for (int i = 0; i < n; i++) {
sum[i] = a[0]; // 空集被包含于所有集合
for (int j = i; j > 0; j = (j - 1) & i)
sum[i] += a[j];
}
这样的复杂度是 $O(3^n)$ 的只能说还不错，但是我们还有更好的做法，灵感来源于求前缀和。
前缀和问题再探
对于低维度的前缀和问题，我们一般采用容斥的方式推导某一项的值，因为维度较低时，我们往往可以视容斥的复杂度是 $O(1)$ 的。
但仔细观察我们会发现这个容斥的过程其实是维度相关的，假设我们要做 $D$ 维前缀和，实际上，我们需要花费 $O(2^D)$ 的时间计算每一个容斥。
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + a[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 1; k <= l; k++) {
sum[i][j][k] = sum[i - 1][j][k] + sum[i][j - 1][k] + sum[i][j][k - 1] -
sum[i - 1][j - 1][k] - sum[i - 1][j][k - 1] - sum[i][j - 1][k - 1] +
sum[i - 1][j - 1][k - 1] + a[i][j][k];
}
但其实我们完全可以换一个方向来求这个前缀和，我们没必要每次都用已经求出的 $D$ 维立方体来推导新的 $D$ 维立方体中元素的和。
例如对于二维的情况我们可以按行先求出每一行的前缀和，然后利用行的前缀和求矩形内的前缀和。
/*
----------------->
----------------->
----------------->
*/
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
line_sum[i][j] = line_sum[i][j - 1] + a[i][j];
}
}
/*
--------|-----|-->
--------|-----|-->
--------v-----v-->
*/
for (int j = 1; j <= m; j++) {
for (int i = 1; i <= n; i++) {
sum[i][j] = sum[i - 1][j] + line_sum[i][j];
}
}
使用已经求出的小矩形，加上新的一行。
再看三维的情况，我们可以先求出每一条线的前缀和，之后求面的前缀和，最后再求小立方体的前缀和。
for (int j = 1; j <= m; j++)
for (int k = 1; k <= l; k++) // 求 j k 相等的每条线上的前缀和
for (int i = 1; i <= n; i++) {
line_sum[i][j][k] = line_sum[i - 1][j][k] + a[i][j][k];
}
for (int k = 1; k <= l; k++) // 求 k 相等的每一个面上的前缀和
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
face_sum[i][j][k] = face_sum[i][j - 1][k] + line_sum[i][j][k];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 1; k <= l; k++) {
sum[i][j][k] = sum[i][j][k - 1] + face_sum[i][j][k];
}
注意到这里其实对于每个三重循环，我们可以任意排列 $i, j, k$ 循环的位置。仔细观察，我们其实是在按照维度依次做前缀和（每次处理了前 $p$ 个维度的前缀和）。
这里我们发现复杂度从原本的 $O(2^D \Pi_{i = 1}^{D} N_i)$ 下降到了 $O(D \Pi_{i = 1}^{D} N_i)$。当维数 $D$ 很大时，这个优化将会非常显著。
高维和和子集和的关系
这里我们注意到，实际上子集和可以按照位数 $D$ 分为 $D$ 个维度（每个维度只有 $0, 1$ 两个取值），而实际上每个子集和对应了一个 $D$ 维超立方的前缀和。这里我们可以完全的将求前缀和的方式搬到这里求子集和。只是细节需要注意，任意一维 $-1$ 的位置可以假想对应了一个 $0$ 的值，于是我们发现我们实质上在处理第 $p$ 维时，只需要注意那些该维为 $1$ 的位置。这里我们用 $dp[i][d]$ 表示超立方体已经处理了下标 $0 \sim d$ 维度时的前缀和。
for (int i = 0; i < (1 << D); i++) {
if (i & 1) {
dp[i][0] = a[i] + a[i ^ (1 << d)];
} else {
dp[i][0] = a[i];
}
}
for (int d = 1; d < D; d++) {
for (int i = 0; i < (1 << D); i++) {
if (i & (1 << d)) {
dp[i][d] = dp[i][d - 1] + dp[i ^ (1 << d)][d];
} else {
dp[i][d] = dp[i][d - 1];
}
}
}
特别的对于每一个跑了 if 的值，一定存在一个对应的集合跑了 else 也就是说，实质上我们是这样更新的
if (i & (1 << d)) {
dp[i][d] = dp[i][d - 1] + dp[i ^ (1 << d)][d - 1];
}
更进一步每一个被更新的 $dp[i][d]$ 都不会再被其他 $dp[j][d] $的元素使用了。
于是我们可以完全的将数组滚动起来
for (int i = 0; i < (1 << D); i++) {
dp[i] = a[i];
}
for (int d = 0; d < D; d++) {
for (int i = 0; i < (1 << D); i++) {
if (i & (1 << d)) {
dp[i] += dp[i ^ (1 << d)];
}
}
}
超集和
对于集合而言，有时我们也希望求出所有超集的和
$$ sum[i] = \sum_{j \supseteq i} a[j] $$即
$$ sum[i] = \sum_{j \& i = i} a[j] $$当我们想求超集和时，我们注意到实际上这里 $0, 1$ 的关系是反过来的。（子集和是包含原点的超立方体，超集和是包含边界超立方体上关于原点对称的顶点的超立方体）
for (int i = 0; i < (1 << D); i++) {
dp[i] = a[i];
}
for (int d = 0; d < D; d++) {
for (int i = 0; i < (1 << D); i++) {
if (!(i & (1 << d))) {
dp[i] += dp[i ^ (1 << d)];
}
}
}
抛开前缀和
抛开维度、高维前缀和等等，我们也可以直接这样定义 $dp[i][d]$：对于集合 $i$ 已经处理了后 $d + 1$ 位的子集的子集和。
更进一步
莫比乌斯变换
沃尔什变换
Next: 《Learning Python》 笔记 第 4 章 介绍 Python 对象类型