【算法】快速沃尔什变换 FWT 从入坑到睡着 ——quhengyi11

快速沃尔什变换 ($Fast Walsh-Hadamard Transform$, 简称 $FWT$)，是一种可以加速集合卷积的算法

会 $FFT$的同学肯定知道，$FFT$加速多项式乘法实际上就是加速了一个卷积。在 $FFT$里，卷积的形式是长这个样子的：

$$C(k)=\sum_{i+j=k}A(i)B(j)$$

而所谓集合卷积又是一个怎样的东西呢？其实它就是长这个样子的

$$C(k)=\sum_{i\times j=k}A(i)B(j)$$

其中 $\times$指的是一个集合运算符

那 $FWT$这东西具体是怎么操作的呢？

让我们来首先回忆一下 $FFT$是怎样操作的：
1. 利用 $dft$将多项式变为点值表示（运用分治思想）
2. 将点值相乘
3. 利用 $idft$将点值变回原来的系数形式

现在我来说一下 $FWT$的思路，其实和 $FFT$是十分相似的：
1. 利用 $FWT$变换将原数组变为点值表示（也要分治）
2. 将点值相乘
3. 利用 $UFWT$变换将点值变回来

这样说似乎有点抽象，总结来说就是将原来的卷积运算变为点值运算，这里我们定义 $\;\cdot\;$为点乘运算符，效果是将两个数组对应位相乘，复杂度是 $\Theta(n)$的，因此我们要寻找一组变换及其逆运算 $FWT()$和 $UFWT()$，使得它满足 $FWT(A) \cdot FWT(B) = FWT(C)$且 $A’=FWT(A)\quad A=UFWT(A’)$

而我们现在的核心问题就是找到这个运算，比较 $exciting$的是，对于每种运算，它的 $FWT$变换往往都有一定的差别（但差别不是特别大）我们先从或运算 $’|’$开始了解这个神秘的变换

首先或运算的 $FWT$是长这样的：
$$A'[i]=\sum_{i|j=i}A[j]$$

我们该如何理解这个式子呢？其实我们可以把 $i,j$都看作一个集合（由二进制数表示），接着我们会发现上面运算的实质就是将 i 中的所有子集求和，我们会发现通过这种变换后 $A’\cdot B’=C’$这个式子是成立的，这里给出证明：

设 $i$为定义域内任意数，则上式变为
$$A'[i] \cdot B'[i]=C'[i]$$
接着将式子展开：
$$(\sum_{i|j=i}A[j])\cdot(\sum_{i|j=i}B[j])=\sum_{i|j=i}C[j]$$
再将右边展开：
$$(\sum_{i|j=i}A[j])\cdot(\sum_{i|j=i}B[j])=\sum_{i|j=i}\sum_{k_1|k_2=j}A[k_1]B[k_2]$$

考虑换元，即：
$$
\begin{array}{c}
i|j&=i\\
i|k_1|k_2 &= i
\end{array}
$$
即 $k_1$和 $k_2$也是 $i$的子集，于是原式化为：
$$
(\sum_{i|j=i}A[j])\cdot(\sum_{i|j=i}B[j])=\sum_{i|k_1=i}\sum_{i|k_2=j}A[k_1]B[k_2]
$$
易知左右两边是相等的

嗯那我们既然已经证明了这个，那现在的问题是如何由 $A$快速通过 $FWT$求得 $A’$

我会枚举子集

那你这个时间复杂度就退化成原来的啦！

考虑类似 $FFT$里面的分治思想。

为了方便分治，我们假设 $A’$数组的长度是 $2^k$的（不足的位数在前面补上 $0$，和 $FFT$差不多的），接着我们将 $A’$分为两半，设 $A’=\{a_1,a_2,\cdots,a_{2^k}\}$，那么 $A_1’=\{a_{2^{k-1}+1}, a_{2^{k-1}+2},\cdots,a_{2^k}\}$，$A_0’=\{a_1, a_2,\cdots,a_{2^{k-1}}\}$

假设我们已经知道了 $A_0′,A_1’$，我们如何求 $A’$呢？

考虑我们当前求的 $A’$的下标是 $k$，则 $A_0′,A_1’$的唯一的不同就在当前最高位，$A_0’$这一位是 $0$,$A_1’$这一位是 $1$，我们可以发现，如果这一位是 $0$的话，根据或的性质，只有 $A_0’$是它的子集（最高位只能填 $0$呀），如果这一位是 $1$的话，那么 $A_1′,A_0’$都是它的子集（最高位随便填呀），因此我们便得到一个这样的函数：
$$A’=merge(A_0′,A_0’+A_1′)$$
其中 $merge(x,y)$能将 $x,y$两个数组拼起来，$+$指的就是按数组下标相加喽。

因此我们就能够用 $\Theta(nlogn)$的复杂度求出 $A’$了

那逆变换怎么搞呢？

其实我们可以根据刚才推出来的东西倒着推回去，我们知道：
$$A_0’=A_0,A_1’=A_0+A_1$$
那么很容易可以推出：
$$A_0=A_0′,A_1=A_1′-A_0’$$

接着用类似上面的方法就能推回去啦~

（感觉自己还是讲的好玄乎呀 QAQ）

对于与运算，异或运算，我们也可以用类似的方法推一遍，这里给出它们最后的公式：

与运算：
$$A’=merge(A_0’+A_1′,A_1′)$$
$$A=merge(A_0-A_1,A_1)$$

异或运算：
$$A’=merge(A_0’+A_1′,A_0′-A_1′)$$
$$A=merge(\frac{A_0+A_1}2,\frac{A_0-A_1}2)$$

与运算跟或运算的推导过程差不多，异或运算的推导我还有点昏（捂脸）

QAQ 蒟蒻的我也只能记一下公式了。