点分树

notes

概述

将点分治的过程离线下来，即将重心相连，可以形成一棵树，称作点分树。它有很好的性质

  • 树的深度为 $O(\log n)$。

  • 所有点子树大小为 $O(n\log n)$。

  • 点分树上 $\texttt{lca}(u,v)$ 一定在原树 $u \leadsto v$ 上（不一定为原树上的 lca）。

对于任意点 $u$，一般会用数据结构维护 $u$ 的子树的对 $u$ 信息，$u$ 的子树对 $fa_u$ 的信息。后者用于容斥。

例题

  • 【模板】点分树 | 震波

    建出点分树。对于查询，枚举 $x$ 在点分树上的祖先，统计祖先的子树对答案的贡献，将重复的容斥掉。

    对于修改，用树状数组维护信息，将 $x$ 在点分树上的祖先都改一下即可。

    时间复杂度 $O(n\log^2n)$，code。

  • [HNOI2015] 开店

    一棵树，点有点权，多次询问，每次询问点权 $<=k$ 的点到 $u$ 的距离和，强制在线。

    由于没有修改，对每个点开个 vector 按权值排序并预处理前缀和，查询时二分一下即可。

  • [ZJOI2015] 幻想乡战略游戏

    在点分树上每次向重心移动一步，最后到达重心，移动次数为 $O(\log n)$。

    考虑重心确定时如何快速计算答案，类似换根 DP，每次跳父亲计算答案即可。

    时间复杂度 $O(n\log^2n)$。

    加一个三度化可以去掉度数 $\le 20$ 的限制

    树的三度化

    对 $u$ 的每个儿子依次加一个节点串起来。

  • 小清新数据结构题

    设根为 $1$，推式子得到

    其中 $siz{[u,1)}$ 为 $u \to 1$ 不包括 $1$ 的 $siz$ 和。树剖简单维护，时间复杂度 $O(n\log^2n)$。

    但是现在在学点分树，考虑点分树做法。还是推式子，考虑将平方拆开。

    对于前面的，需要快速查询 $\sum_{x}a_xdis(x,u)$。

    对于后面的，它和根没有关系，初始值是好求的，当 $a_u+v$ 时，它增加 $2v\sum_{x}a_xdis(x,u)$。

    点分树，时间复杂度 $O(n\log n)$。

  • ❄ ​[Ynoi2011] 成都七中

    对于询问 $(l,r,u)$，可以将每个点到 $u$ 路径上的最大/小编号预处理出来，记为 $(x,y)$。

    那么点 $(x,y)$ 与 $u$ 在同一个连通块当且仅当 $l \le x,y \le r$。扫一遍求解，时间复杂度 $O(mn)$。

    只要 $u,v$ 在同一连通块中，那么 $(l,r,u)$ 与 $(l,r,v)$ 答案相同。

    建出点分树，求出点分树上与 $u$ 在同一连通块的最浅点 $v$，此时询问变为 $(l,r,v)$，好处是点分树的子树和为 $O(n\log n)$。

    对于 $v$ 的求解可以在点分树上暴力往上跳，用倍增维护路径最大/小编号，还可以预处理点分树上每个点到祖先节点路径的最大/小编号。

    一个点会挂多个询问，离线树状数组求解，时间复杂度 $O(n\log^2n)$。

  • Iqea

    保证剩余部分也连通。

    考虑将极长行连通块缩成一个点，将相邻点连边，形成一棵树。

    树上动态加点，求距离最小点，考虑点分树。

    考虑如何通过中间点计算答案，需要计算某点到特定连通块的距离，用 bfs。

    拆式子，需要对连通块每个点维护前后缀最小值。

  • ❄ ​[WC2014] 紫荆花之恋

    需要每加入一个点时将与它相关的点对的数量求出来，再加入该点。

    如果不强制在线，那么可以先建出点分树。需要支持加入，查询比 $v$ 小的数的个数。可以用平衡树。

    还有一种根号分治的做法。维护两个 vector A,B，在 A 中暴力加入点 $v$，若 $|A| > S$ 那么对 A,B 进行归并排序，将 A 清空。查询时在 A,B 中二分即可。

    由于强制在线，考虑设计一个平衡因子 $\alpha$，若存在 $siz_u > \alpha siz_{fa_u}$，那么将 $fa_u$ 的子树重构，这样来维持点分树的高度为 $O(\log n)$。取 $\alpha=0.9$ 较优。

    取 $S=\sqrt{n}$ 可以做到 $O(n\sqrt{n}\log n)$。

    code

参考