后缀自动机学习笔记
写在前面 推荐hihocoder上的讲解，可以说是十分清楚了。 用好后缀自动机不是十分容易，但看完本文的总结应该能至少达到签到水平…
多维快速傅里叶变换
以下内容摘自《算法导论》思考题30-3 我们可以将一维离散傅里叶变换推广到d维上，这时输入是一个d维的数组A=(aj1,j2,…,jd)A=(a_{j_1,j_2,\dots,j_d})A=(aj1,j2,…,jd)，维数分别为n1,n2,…,ndn_1,n_2,\dots,n_dn1,n2,…,nd，其中n1n2…nd=nn_1n_2\dots n_d=nn1n2…nd=n。
快速傅里叶变换学习笔记
一、写在前面 最近数字图像处理课正在学快速傅里叶变换，发现自己对此理解的还不是很到位。于是借此机会，对照着《算法导论》，对这部分内容啃一啃。 两个nnn次多项式相加的最直接方法所需的时间是O(n)O(n)O(n)，但是相乘的最直接方法所需的时间为O(n2)O(n^2)O(n2)。用快速傅里叶变换（Fast Fourier Transform，FFT）可以使多项式相乘的时间复杂度降低为O(nlogn
莫队算法总结
写在前面 莫队算法用于离线解决一类区间问题。 普通莫队 如果我们已知查询为区间[l,r][l,r][l,r]的答案，并且能在O(1)O(1)O(1)的时间内通过添加或删除一个元素得到[l−1,r],[l+1,r],[l,r−1],[l,r+1][l-1,r],[l+1,r],[l,r-1],[l,r+1][l−1,r],[l+1,r],[l,r−1],[l,r+1]的答案，那么就可以考虑使用莫队