学习心得 - 数据结构 - 点分治 & 点分树

ExFish · 2025-08-20 19:52:58 · 算法·理论

点分治

一种维护树上问题的算法，要求是一次查询的路径问题。这个算法通过找重心，然后从重心开始分治子树，再统计答案，而计算问题答案的算法。

具体的，我们每一次从重心开始分治，复杂度总是优于 \mathcal O(n\log_2n)，这是因为重心的性质。这样，大部分的点就可以被扫过，就可以进行维护树上信息，查询了。

点分树

那么当查询变成 q 次怎么办呢？可以考虑连接重心，构造出一颗点分树。树高是 \le \log_2n。并且，原树上的 u，v 的 \text{LCA} 一定在 u\to v 的路径上。这棵树的形态比较优。就可以快速求出答案。