说明
本文基于 ZR 黄老板的课堂讲授整理而成，系课堂笔记。如有疏漏，责任在笔者。
众所周知，二维前缀和有两种写法。
第一种是利用容斥原理。
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++)sum[i][j] = a[i][j];
for (int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)if (i > 1) sum[i][j] += sum[i - 1][j];
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)if (j > 1) sum[i][j] += sum[i][j - 1];
随着维数的增加，容斥的做法会很复杂。于是我们更加普遍地使用第二种。
考虑进行状态压缩。我们能否用一维来表示二维呢（\(n \times m \le 10^6\)）？
我们考虑将二维平面断成行，使之首尾相接，于是我们发现，\(a_{i, j}\) 等价于 \(a_{mi + j}\)。
那三维呢（\(n \times m \times t \le 10^6\)）？
考虑将一个三维几何体“切”成二维平面，转化为二维问题。于是有 \(a_{i, j, k}\) 等价于 \(a_{mti + mj + k}\)。
我们假设每个维度的长度为2，即每一维的下标范围为 \(\{ 0, 1 \}\)。
我们发现对于 \(n\) 维，上述压缩后的一维下标为 \(j = 2^n \times i_n + 2^{n - 1} \times i_{n - 1} + \cdots + 2 \times i_1 + 2\times i_0\)，等式右边等价于 \(( \overline{i_n i_{n - 1} \cdots i_1 i_0} )_2\)，而这就是 \(j\) 的二进制下表示。
也就是说，我们可以用一个整数来表示 \(k\) 维数组的下标（前提是每个维度的长度为 2）。
于是就可以对三维前缀和进行改写。
// 修改前
for (int i = 0; i <= 1; i++)for (int j = 0; j <= 1; j++)for (int k = 0; k <= 1; k++)if (i > 0) a[i * 4 + j * 2 + k] += a[(i - 1) * 4 + j * 2 + k];
for (int i = 0; i <= 1; i++)for (int j = 0; j <= 1; j++)for (int k = 0; k <= 1; k++)if (j > 0) a[i * 4 + j * 2 + k] += a[i * 4 + (j - 1) * 2 + k];
for (int i = 0; i <= 1; i++)for (int j = 0; j <= 1; j++)for (int k = 0; k <= 1; k++)if (k > 0) a[i * 4 + j * 2 + k] += a[i * 4 + j * 2 + (k - 1)];// 修改后
for (int x = 0; x < 8; x++)if ((x & 4) > 0) a[x] += a[x - 4];
for (int x = 0; x < 8; x++)if ((x & 2) > 0) a[x] += a[x - 2];
for (int x = 0; x < 8; x++)if ((x & 1) > 0) a[x] += a[x - 1];
将这三个 for 合并，并扩展至 \(n\) 维，得到如下代码。
int n = 1 << k;
for (int y = 1; y < n; y *= 2)for (int x = 0; x < n; x++)if (x & y) a[x] += a[x - y];
这也就是 快速莫比乌斯变换 (Fast Mobius Transform, FMT） 求子集和的实现，时间复杂度 \(O(n \log n)\)。