• 周日. 9月 25th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

对点分治的一些新理解

admin

11月 28, 2021

点分治算法分析

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

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

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

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

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

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

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

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

注意的点

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

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

发表回复

您的电子邮箱地址不会被公开。