Summary - 分治

本文旨在总结数种分治算法。

1.区间分治：当需要对所有区间统计答案时，可以考虑这种分治。具体来说，在处理\([l,r]\)内的所有区间时，分三类考虑：跨过\(mid\)的，完全在\(mid\)左边的，完全在\(mid\)右边的。如果可以\(O(m)\)或\(O(m\log m)\)处理第一类情形（\(m=r-l+1\)），然后用分治处理另外两类情形，就可以在\(O(n\log n)\)或\(O(n\log^2 n)\)的时间内解决问题。

2.根号分治：这似乎不算一类典型的分治，但是它有分治这个名字。这种算法更像是一种思想，即分类讨论。当我们需要对\(k=1,2,...,n\)统计答案时，可能可以想到多个算法，某些复杂度为\(k\)的多项式级别，某些复杂度为\(\frac{1}{k}\)的多项式级别，那就可以对不同的\(k\)采用不同的算法，并取合适的分界值，最优化时间复杂度（往往是\(O(n\sqrt{n})\)）。

3.点分治：处理树上路径统计问题的利器。