分治FFT
分治FFT用于快速计算以下类型的式子： \[f[n] = \sum _ {i = 0} ^ {n - 1} f[i]g[n - i]\] 这个式子与正常的\(FFT\)卷积式不同，可以发现\(f\)的每一项计算都需要前面所有项的信息，所以无法在一次\(FFT\)内将\(f[1]到f[n]\)的值计算完成。如果使用FFT暴力计算的话，时间复杂度为\(O(n ^ 2logn)\)，这通常是不能被接受的复杂度。
所以我们采用CDQ分治的思想，对于\(f[l] \cdots f[r]\)的值，我们先计算\(f[l] \cdots f[mid]\)的值，然后计算\(f[l] \cdots f[mid]\)的部分对\(f[mid + 1] \cdots f[r]\)的贡献，最后计算\(f[mid + 1] \cdots f[r]\)的值。
对于边界条件我们不需要去考虑，因为一个位置的值不会对自己产生贡献。
那么需要解决的就是如何计算\(f[l] \cdots f[mid]\)对\(f[mid + 1] \cdots f[r]\)的贡献。
首先考虑在\([mid + 1,r]\)范围内的某一个数\(x\)，\([l,mid]\)区间对其的贡献为： \[w[x] = \sum _ {i = l} ^ {mid} f[i]g[x - i]\]
为了方便推导，我们把求和的范围扩大到\([l,x - 1]\)（此时设\(f[mid + 1] \cdots f[r]\)为\(0\)），即： \[w[x] = \sum _ {i = l} ^ {x - 1} f[i]g[x - i]\]
然后我们设\(a[i] = f[i + l],b[i] = g[i + 1]\)，此时式子变化为： \[w[x] = \sum _ {i = 0} ^ {x - l - 1} a[i]b[x - l - 1 - i]\]
发现等号右侧就是一个基本的FFT卷积，设卷积得到的数组为\(z\)，可得： \[w[x] = z[x - l - 1]\]
然后我们把\(w[mid + 1] \cdots w[r]\)叠加到\(f[mid + 1] \cdots f[r]\)上就可以了
对于\([l,r]\)区间的FFT，我们需要计算的数组长度为\(r - l - 1\)，即单次分治中的复杂度为\(O(nlogn)\)，总复杂度\(T(n) = T(n / 2) + O(nlogn) = O(nlog ^ 2n)\)