UOJ Logo cjLJY的博客

博客

使用根号分治代替伸缩树的一些想法

2022-09-09 21:58:31 By cjLJY

简介

本文主要内容是给出一种不需要科技(伸缩树)的,支持强制在线 $O(\sqrt n)$ 树链加,$O(1)$ 查询树链和(或 $O(1)$ 修改,$O(\sqrt n)$ 查询),且空间 $O(n)$ 的简单算法。

需要的前置知识仅有:根号分治、虚树、序列分块。

算法内容

不妨考虑修改 $O(1)$ 询问 $O(\sqrt n)$ 的版本,另一版本做法类似不再赘述。

显然问题可以转化给一棵树,要求支持 $O(sqrt(n))$ 将点到根路径上每个点加上 $v$,$O(1)$ 查询一个点到根路径上点的权值和。

不妨称子树大小大于 $\sqrt n$ 的点为黑点,其余点为白点。

考虑所有没有黑色儿子节点的黑点构成的虚树,不难证明虚树的大小是 $O(\sqrt n)$ 级别的(简证:叶子节点个数不超过 $\sqrt n$)。

我们发现修改和询问的树链都是这么个情况:

1.(1)走一段白点(2)走虚树上一条边的一部分(一条虚树边内部的某个前缀)(3)走虚树上一些整边。

分别考虑:

(1)类型的修改对(1)类型查询的贡献:

再修改时,找到路径上深度最浅的白点,暴力计算子树中每个点的 $ans$,修改时直接查 $ans$,做到修改 $O(\sqrt n)$ 询问 $O(1)$。

(3) 类型的修改对 (3) 类型查询的贡献:

要求每个虚树边上进行 $O(\sqrt n)$ 前缀加 $O(1)$ 查询前缀和。容易用序列分块做到。

其余类型的贡献:

就是对虚树边的各种 tag 进行修改和查询,在修改的时候直接暴力修改所有虚树边的 tag,询问时直接调。修改 $O(\sqrt n)$ 询问 $O(1)$。

至此问题得以解决。

拓展

对于部分询问不满足可减性的也不是完全不能搞,比如说:

1.$\sqrt n$ 链加,查询点到根最小值 $O(1)$。

使用上述算法并没有什么难度,甚至细节比链加链求和要少很多。

不过如果询问是树链询问,则需要解决 $O(n)$ 预处理一棵树,$O(1)$ 查询树链最小值的子问题,大概是可以做的,但相对来讲会非常繁琐。

搞不准有更加棒棒的玩法,大佬们可以尝试。

评论

zx2003
萌新提问,什么是伸缩树啊?

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。