高维前缀和
一维前缀和是形如这样的递推式：
s_i=s_{i-1}+a_i
它也可以扩展到二维：
s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}
比较容易发现它是个容斥的形式。那么我们扩展到 k 维时，这个式子就会有 2^k 项，计算的复杂度是 O(n2^k)。这有时会很慢。
我们考虑另一种方法，按维迭代。具体地，我们枚举每一维，从这一维的方向求一边前缀和。神奇的是这样做是对的，，复杂度降到了 O(nk)。
举个例子，三维时可以这么写：
for (int i=1; i<=r; i++)
for (int j=1; j<=c; j++)
for (int k=1; k<=h; k++)
s[i][j][k]=s[i-1][j][k]+a[i][j][k];
for (int i=1; i<=r; i++)
for (int j=1; j<=c; j++)
for (int k=1; k<=h; k++)
s[i][j][k]=s[i][j-1][k]+a[i][j][k];
for (int i=1; i<=r; i++)
for (int j=1; j<=c; j++)
for (int k=1; k<=h; k++)
s[i][j][k]=s[i][j][k-1]+a[i][j][k];
维数很多时，我们当然不需要复制粘贴好几遍，直接状态压缩一下就可以了。
比如子集求和，这实际上可以看成是求每一维都只有 \{0,1\} 的 k 维前缀和。那么我们可以这么写：
for (int i=0; i<k; i++)
for (int s=0; s<1<<k; s++)
if (s&1<<i) f[s]+=f[s^1<<i];
这也就是子集 DP 了。
快速沃尔什变换（FWT）
FWT 是一种用于计算位运算卷积的算法。
位运算卷积大概是形如这样的式子：
C_k=\sum_{i\oplus j=k}A_iB_j \tag{1}
其中 \oplus 表示一种指定的位运算（按位与，按位或，按位异或）。二进制数可以表示一个集合，所以 FWT 也可以认为是处理集合的某种卷积运算。
转换点值
要快速计算上面的式子，我们可以参考 DFT 的做法，将叉乘转化为点乘。将给出的多项式看作向量，我们希望构造出一个向量到向量的映射 DWT，使得
DWT(C)_i=DWT(A)_i\cdot DWT(B)_i \tag{2}
具体地，我们希望构造一种线性变换，也就是向量乘上一个矩阵的形式，这样更方便进一步处理。所以我们不妨设
DWT(A)_i=\sum_{j=0}^{n-1}c_{i,j}A_j \tag{3}
其中 c 是变换系数。我们现在需要知道这个变换系数是什么。
联立 (1)(2)(3) 得
\sum_{t_1=0}^{n-1}\sum_{t_2=0}^{n-1}c_{i,t_1\oplus t_2}A_{t_1}B_{t_2}=\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c_{i,j}c_{i,k}A_jB_k
因此，有 c_{i,j}c_{i,k}=c_{i,j\oplus k}。
可以证明逆变换的矩阵就是 c 矩阵的逆。由于位之间的独立性，还可以得出
c_{i,j}=c_{i_0,j_0}c_{i_1,j_1}\cdots
其中下标表示二进制中的第几位。
实现时，我们仍采用分治的思想。
DWT(A)_i=\sum_{j=0}^{n-1}c_{i,j}A_i=c_{i,0}\sum_{j=0}^{n/2-1}c_{i',j'}A_j+c_{i,1}\sum_{j=n/2}^{n-1}c_{i',j'}A_j
其中 i',j' 分别是 i,j 去掉二进制首位的结果。那么我们已经可以将其分解成两个子问题了：
\begin{array}{c}DWT(A)_i=c_{0,0}DWT(A_0)_i+c_{0,1}DWT(A_1)_i\\DWT(A)_{i+\frac{n}{2}}=c_{1,0}DWT(A_0)_i+c_{1,1}DWT(A_1)_i\end{array}
所以我们只需要求出一个 2\times 2 的矩阵就好了。根据上面的约束，是可以人类智慧构造出这个矩阵并求出它的逆的，比如对于按位或运算，它的矩阵是 \bigl(\begin{smallmatrix}1 & 0\\ 1 & 1\end{smallmatrix}\bigr)，它的逆矩阵是 \bigl(\begin{smallmatrix}1 & 0\\ -1 & 1\end{smallmatrix}\bigr)。其它的运算会在下面的内容里一并说。
高维扩展
准确地说这似乎并不能叫“高维扩展”，因为这只是扩展了每一维的值域而已。
上面讲的位运算卷积，每维的值域是 \{0,1\}。现在我们将其变成 [0,k)，即模 k 的剩余系，会发生什么呢？
我们让按位与对应按位取 \min，按位或对应按位取 \max，按位异或对应按位相加模 k。发现这在二进制下是等价的。这时的位运算卷积也可以用构造矩阵的方式转换点值，矩阵的构造同样满足上面的性质。
我们先人类智慧构造出 k=4 时按位或的一种矩阵（过程略）：
\begin{pmatrix}1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1\end{pmatrix}
它的逆元：
\begin{pmatrix}1 & 0 & 0 & 0\\ -1 & 1 & 0 & 0\\ 0 & -1 & 1 & 0\\ 0 & 0 & -1 & 1\end{pmatrix}
是不是很有规律？它的变换矩阵是下三角矩阵，而它的逆也有比较明显的规律。如果你完全明白了上面的分治过程，你可以发现这两个矩阵实际上就对应了高维前缀和和高维差分。也就是说，每维值域为 k 的或运算 DWT / IDWT 实际上就是求高维的前缀和 / 差分的过程。那么回到二维，这时的或运算 DWT 就是子集和，它和子集 DP 是等价的。
那么与之对应，按位与运算的变换矩阵是上三角矩阵，它的逆矩阵也是或运算的逆矩阵的转置。同时，它的 DWT 和 IDWT 分别对应了求高维后缀和与差分。
我们现在可以归结一下这两种位运算卷积的本质了。仍然把一个数看成集合，而高维时就看成多重集。以按位或为例，那么有
DWT(A)_i=\sum_{j\subseteq i}A_j
把两个子集和点乘起来，得
DWT(A)_i\cdot DWT(B)_i=\sum_{j\subseteq i}A_j\sum_{k\subseteq i}B_k=\sum_{j\cup k\subseteq i}A_jB_k=DWT(C)_i
注意这里的符号都是子集符号，而不是等于。要把它变成等于，就需要做一次 IDWT，也就相当于一次高维差分或者是容斥。发现了这个规律以后，FWT 做到事情就不只是位运算卷积，还可以做一些别的事。这里给出一道例题：CF772D. Varying Kibibits，这里是 我的题解。
异或运算
异或和上面两种有很大区别，主要体现在它的变换系数上。这里可以先给出 k=2 时的变换矩阵 \bigl(\begin{smallmatrix}1 & 1\\ 1 & -1\end{smallmatrix}\bigr) 以及它的逆 \bigl(\begin{smallmatrix}0.5 & 0.5\\ 0.5 & -0.5\end{smallmatrix}\bigr)。
写出来可以发现和 FFT 的写法几乎一样。考虑到这里的卷积是下标相加后取模，这可能和多项式卷积有相似的性质。实际上，它的变换矩阵也是相同的范德蒙德矩阵（矩阵就不画了）。
当运算只有一维时，这个东西就是 FFT 了。实际上扩展值域的异或 FWT 也就是 FFT 的高维扩展（DFT 本身是循环卷积）。
那么我们同样可以用分治的方法做，只不过不是一分为二，而是每次分为 k 份。逆变换就使用逆范德蒙德矩阵就可以了。但是做这种题的时候一定要注意精度。
冷滟泽的个人博客