动态点分治入门随讲

扯两句淡

为什么叫入门随讲呢……因为我也刚学完啊

前置技能

点分治(这不是要学动态点分治吗)

线段树(会点分治不会线段树？)

其实线段树是来帮助理解的。

为好友打广告(利用好友优秀博文提升×格)

句句经典……在点分上没有一定造诣还真写不出来。

墙裂推荐一观，文笔和思想都比某hr好多了。

浅谈对点分治的一些理解——qt666

正文

引入

点分治是一种人人喜欢的算法。它含钙高，吸收好思想比较简单，代码实现也不难，复杂度瓶颈在统计跨重心root的链对答案的影响/贡献。

但是点分治的缺点是很明显的：它只能做离线问题！换句话说，它不支持修改操作。

这个时候就需要动态点分治来帮帮忙了。

算法原理

这个时候我们已经对点分治的理解很深了。它通过巧妙地在k级重心处划分，把树上的路径划分成了两类：经过重心的和不经过重心的。

之所以复杂度有保证，是因为每个点作为链端点只会被统计log次。

带修改的话，暴力肯定是询问一次做一次点分。

注意到修改的基本是点权之类的而不是树的形态。换言之，每次的点分过程是一样的！

然后又想到每个点只会被统计log次——胡不重构此树乎？

讲清楚点：既然每次修改只会改一个点，只会把它作为端点的链的信息改掉。

(要是你改一个点会引起多个点改动也不像是树分治题而更像传统数据结构题)

其他的点的信息该是多少还是多少，是不变的过往，是永恒的黑暗与孤独——打住。

多次处理重复相同信息，是必不可能被我们所称赞的。而这些信息总的数量级又只有O(nlogn)级别。

为什么不把它事先保存，然后对于每次修改，O(logn)级别地暴力一一修改呢？

每次查询，要么直接取，要么暴力跳一个点的重心祖先链，复杂度也很优秀。

即：预处理点分治一遍，把分级重心树搞出来，把信息存进去。

每次操作，修改即想办法修改自己到祖先重心链上的信息即可。

询问呢，你都维护了这么多东西了，也是想办法快速求就可以了。

比如说取最大值，那就开堆嘛(ZJOI捉迷藏)。

再比如说HNOI开店，用vector动态申请空间，排序一下，每次询问暴跳祖先。

说起来好像很简单，实现起来却是如人饮水冷暖自知。

剩下的我一时也不知道还能讲什么了？……

送一句话：树上的动态点分治就相当于序列上的线段树。

忘记是从哪个神犇那蒯的了……

最后也送一点套路

两点lca什么的别用倍增了，用欧拉序列+ST表预处理O(1)搞定。

还有记得把log也预处理出来，系统超慢。

开堆开桶之类的，vector或new