「学习笔记」动态点分治
引子
点分治是个好东西, 可万一树上的权值需要修改呢......
算法过程
- 点分治, 计算出初始数据.
- 构建点分树.
- 在点分树上进行数据维护.
点分树 : 把原树在点分治时的各级重心连接起来的数据结构, 称为点分树.
它有一个非常优美的性质 : 树高 规模为 (log n).
根据这个性质, 我们就可以在修改点权时, 在点分树上一层一层往上走, 逐个维护每个祖先的数据.
并且, 我们还可以得到 (sum_{u in V} size[u] = n log n), 其中 (V) 是树的点集, (size[u]) 是点 (u) 在点分树上的子树大小.
可以这样理解 : 由于点分树的树高为 (log n), 所以每个节点都只会被覆盖 (log n) 遍.
有了这个性质, 我们就可以实现一些 丧心病狂 梦寐以求的操作, 比如对每个点开一个优先队列.
个人认为, 动态点分治的关键在于 : 找出点分治的过程中我们需要的数据, 并使用恰当的数据结构来维护这些数据.
如果解决了这个问题, 那么动态点分治的题目就迎刃而解了. 当然, 对于某些题目, 码量还是个问题.
题目
[ZJOI2007]捉迷藏 (这题动态点分治不是最优解, 在洛谷上交最后一个点大概率会 T, 可以在 bzoj 上交) (bzoj1095)
参考资料
动态点分治 by ZZQ
题解 P2056 【[ZJOI2007]捉迷藏 by ywy_c_asm