前两天刚学了动态点分治（理解的那叫一个费劲），来简单讲一讲。
动态点分治，其实是一个非常静态的数据结构——点分树。所谓点分树就是在点分治过程中，把每层的重心连起来建成一棵树。为什么把动态点分治单独拿出来，就是因为动态点分治在建完点分树之后几乎和点分治没有一点关系了。。。
点分树的树高是\(O(logn)\)的，这也意味着在点分树上你可以从上到下反复横跳暴力跳然后轻松地访问某个点到根之间的所有信息。
但是！点分树相当于破坏了原树的结构，原树的很多性质到点分树上就不复存在，特别是跟子树有关的事情动态点分治是万万不可的（因为可能在原树上是你儿子的点到了点分树上就成了你的祖先了）。因此，我们只能在一些不那么关心树的形态的题上使用点分树，例如路径等等（其实是我做题太少了举不出例子了）。
大致思想呢，就是你每次能确定答案在哪棵子树内，然后跳到这棵子树的重心上（在点分树上也就是它的儿子），这样最多\(O(logn)\)次就可以找到答案。
下面给出一些动态点分治的题目：
原文：https://www.cnblogs.com/With-penguin/p/12724998.html