前言
本人在 HL 集训时爱上了根号算法,遂开此坑。
所有根号算法都有一个共性:与暴力算法息息相关。但它们并不是拙劣的暴力,而是优美的暴力。所以根号算法也被称之为“暴力美学”。
根号分治就是一个典型的根号算法。当题目性质与 \(x\) 和 \(\frac{n}{x}\) 都有关时,我们可以找到一个分界点 \(B = \sqrt{n}\) 进行分治,一部分直接暴力,另一种部分利用上述性质使用某种方式来处理,这样我们就达到了一种微妙的平衡。
通过上面的例子,我们知道了大部分根号算法的另一个特点:在两个信息之间寻找平衡。分块思想也是如此。它将区间 \([1, n]\) 分为若干个长度为 \(\sqrt{n}\) 的块,每次区间操作(或询问)时,没有完全覆盖一个块的“边角料”可以暴力,而完全覆盖它的部分可以直接对整个块进行打标记等操作。前者虽然理论复杂度是 \(\mathcal{O}(n)\),但是需要暴力的“边角料”只有 \(\mathcal{O}(\sqrt{n})\) 个点,所以它的实际复杂度是 \(\mathcal{O}(\sqrt{n})\)。后者虽然理论复杂度较低(一般为 \(\mathcal{O}(\text{ploy}{\log n})\),为了方便,这里看做 \(\mathcal{O}(1)\)),但是它需要对 \(\mathcal{O}(\sqrt{n})\) 个块进行操作,所以它的实际复杂度也是 \(\mathcal{O}(\sqrt{n})\)。可以看到,分块在块长和块的数量中找到了平衡,它也将单次操作复杂度维持在了 \(\mathcal{O}(\sqrt{n})\)。
莫队是一种特殊的根号算法,它将操作(或询问)离线,由上次的结果进行暴力修改移动,得到了这次的结果。这种算法还将操作(或询问)按照某种方式排序,使得每次暴力修改移动的次数不超过 \(\mathcal{O}(\sqrt{n})\)(有的是 \(\mathcal{O}(n ^ {\frac{3}{2}})\)),进而保障了复杂度。
当然,根号算法也可以和其他算法(比如二分)结合,这样会使得复杂度在根号内或外带若干支 \(\log\)。
总体来说,根号算法避免了使用递归数据结构,使得程序常数较小。当然,根号的复杂度不够优秀并且较难优化,这也是它最大的问题。所以,熟练掌握根号算法并不是你放弃学习其他数据结构的理由。
(其实还有整除分块,但是它属于数学内容,所以就不放在这里啦。)