分治的延伸应用
应用场景
优化合并
假设将两个规模 \(\frac{n}{2}\) 的信息合并为 \(n\) 的时间复杂度为 \(f(n)\)，用主定理分析时间复杂度 \(T(n) = 2 \times T(\frac{n}{2}) + f(n)\)。
能直观的看出优化程度还是很大的。
归并排序中 \(f(n) = O(n)\)，则 \(T(n) = O(n \log n)\)。
特别的当 \(f(n) = O(n^k),k \ge 2\) 时，我们通常不会使用分治，因为无法优化时间复杂度。
优化合并通常应用于哈夫曼树、线段树。
优化计数
我们对长度为 \(n\) 的序列 \(\{a_n\}\) 统计有多少对 \((i,j)\)，使得 \(i < j\) 且 \(a_i > a_j\)。
可以使用分治求解 \([l,r]\) 一段内逆序对数。
我们令 \(\text{mid} = \frac{l + r}{2}\)，分别处理 \([l,\text{mid}]\) 和 \([\text{mid},r]\) 即可。
代码实现的注意事项：
-
特判分治的递归边界。
-
若用到临时数组，确保其得到清空，切勿盲目 \(\text{memset}\)。