对点分治的一些新理解

点分治算法分析

点分治用来处理有关数上路径问题。

所有路径对答案的贡献其实可以分成,所有过一点的路径+所有不过这点的路径。

不过这点的路径怎么算?可以以这点为根到它的子树里分治解决。

所以现在问题只有:1、所有过这点的路径怎么解决?2、复杂度怎么保证?

问题二:可以每次分治时以重心为根。这样最多分治\(logn\)

重心:满足以此为根,所有儿子子树大小的最大值最小的节点。重心有一个性质:以重心为根的树,所有重心的儿子子树的大小一定小于\(\frac{n}{2}\)。这个性质的证明跟某一经典的贪心证明很像(好像是把数轴上的所有物品移到哪个物品上的花费最小)。

这个性质保证了最多分\(logn\)层。

问题一:方法不是重点,点分治重点在于分治,把求书上路径问题转化成求树上过一个点路径的问题,而且代价只是复杂度多了一个\(log\)

注意的点

计数问题中一个一个去记答案是很蠢的,除非答案的数量级很小。

除了计数问题之外,还有所有关于通过根节点路径的最优化问题(选哪个为根),通常这类问题有单调性,可以判断答案在某个子树里。然后普通方法复杂度不对,用点分治最多\(logn\)层子树的性质优化算法。

对点分治的一些新理解

上一篇:关于引用mshtml的问题


下一篇:Git