点分治 笔记

点分治学习笔记

以后会有动态点分治的

点分治是一类可以快速静态统计满足限制要求的路径的算法。

树上的根任选也不会影响到路径,我们假定现在的根为 $p$。那么对于一条路径有如下两种情况:

  • 经过了 $p$
  • 在 $p$ 的子树内

要进行点分治的前提是能够快速统计_经过了 $p$_ 的路径。在此前提下,对第二种情况进行分治,直接递归计算即可。

每次选择子树的重心进行递归分治,这样子一个结点最多会被访问到 $\log_2 n$ 次(例如被排序的次数),因此复杂度就有了保证。

最后修改:2019 年 08 月 16 日 10 : 41 AM

发表评论