另一種卷積
多項式乘法的卷積是這樣的：
Ci=∑j+k=iAjBk
然而還有種神奇的卷積（ ⊕ 是位運算）：
Ci=∑j⊕k=iAjBk
FWT可以快速求這種卷積。
快速沃爾什變換
因為FFT用了系數 → 點值，用點值快速求卷積，再點值 → 系數的方法，是以我們也想讓沃爾什變換具有這樣的特點，于是開始構造。
離散沃爾什變換
定義 DWT(A) 是向量 A 經過離散沃爾什變換得到的向量，令變換系數為 f(i,j) ，那麼：
DWT(A)i=∑j=0n−1Ajf(i,j)DWT(A)iDWT(B)i=DWT(C)i
這樣沒法求 f(i,j) 啊，我們來推一下：
DWT(A)iDWT(B)i=DWT(C)i∑j=0n−1Ajf(i,j)∑k=0n−1Bkf(i,k)=∑t=0n−1Ctf(i,t)∑j=0n−1∑k=0n−1AjBkf(i,j)f(i,k)=∑t=0n−1∑j⊕k=tAjBkf(i,t)=∑t=0n−1∑j⊕k=tAjBkf(i,j⊕k)∑j=0n−1∑k=0n−1AjBkf(i,j)f(i,k)=∑j=0n−1∑k=0n−1AjBkf(i,j⊕k)
也就是說 f(i,j)f(i,k)=f(i,j⊕k) 。
然後就可以對不同的位運算求出不同的變換系數，直接上結論：
and:f(i,j)=[i and j=i]or:f(i,j)=[i and j=j]xor:f(i,j)=(−1)count(i and j)
其中 count(i) 表示 i 在二進制下 1 的個數。這些怎麼得到的？翰爺表示：
并不知道是怎麼來的，但是容易驗證是對的。
這裡就說明一下比較神奇的 xor （ and 和 or 很容易驗證）：
f(i,j)f(j,k)=(−1)count(i and j)+count(i and k)f(i,j xor k)=(−1)count(i and (j xor k))
count(i and j)+count(i and k) 求的是 i 和 j 共有的 1 的數量加上 i 和 k 共有的 1 的數量，我們再考慮下面那個式子表示什麼。因為異或相同為 0 ，不同為 1 ，那麼隻有當 j 和 k 某位上不同時才有貢獻，和上面的式子相比，消去了 j 和 k 某位上均為 1 的貢獻，即 −2k ，不改變奇偶性，是以是相等的。
f(i,j) 有一個很重要性質：可以二進制拆分。用 ik 表示 i 二進制下的第 k+1 高位，則：
f(i,j)=f(i0,j0)f(i1,j1)f(i2,j2)⋯f(ilen−1,jlen−1)
接下來開始考慮離散沃爾什變換（ n 補到 2k ）：
DWT(A)i=∑j=0n−1Ajf(i,j)=∑j=0n2−1Ajf(i,j)+∑j=n2n−1Ajf(i,j)=∑j=0n2−1Ajf(i0,j0)f(i[1,len−1],j[1,len−1])+∑j=n2n−1Ajf(i0,j0)f(i[1,len−1],j[1,len−1])=f(i0,0)∑j=0n2−1Ajf(i[1,len−1],j[1,len−1])+f(i0,1)∑j=n2n−1Ajf(i[1,len−1],j[1,len−1])
喜聞樂見的規模減半了，于是( i∈[0,n2) )：
DWT(A)i=f(0,0)DWT(AL)i+f(0,1)DWT(AR)iDWT(A)i+n2=f(1,0)DWT(AL)i+f(1,1)DWT(AR)i
和FFT很像啊，隻不過FFT是奇偶拆半，而FWT是左右拆半。正因為FWT是左右拆半，直接疊代就可以了，不需要和FFT一樣二進制翻轉。
逆沃爾什變換
根據離散沃爾什變換得到的遞歸式，我們發現隻需要解一下二進制一次方程就可以了。
模闆
inline void FWT(int *a,int n,int f){
for (int k=;k<n;k<<=)
for (int i=;i<n;i+=(k<<))
for (int j=;j<k;j++)
if (f==){
int x=a[i+j],y=a[i+j+k];
//and:a[i+j]+=a[i+j+k];
//or :a[i+j+k]+=a[i+j];
//xor:a[i+j]=x+y;a[i+j+k]=x-y;
} else{
int x=a[i+j],y=a[i+j+k];
//and:a[i+j]-=a[i+j+k];
//or :a[i+j+k]-=a[i+j];
//xor:a[i+j]=(x+y)/2;a[i+j+k]=(x-y)/2;
}
}