外观
2026-09-03
点分治的主要思想是,选择一个点以后将与其相连的子树看作若干个块,进行分治,然后将原问题转换为每一块内部的问题和经过这个点的问题。 每次都会选择树的重心,这样与其相连子树最大不超过 n2\frac n22n,最多经过 logn\log nlogn 层后节点数变为 111。
一个需要注意的地方是,树的重心定义为与其相连子树最大大小最小,至于重心相连子树大小 ≤n2\leq \frac n2≤2n 可以通过反证得到。
版权归属:lyrgo
许可证:署名 4.0 国际 (CC-BY-4.0)