简介

本文主要内容是给出一种不需要科技（伸缩树）的，支持强制在线 $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)$ 查询树链最小值的子问题，大概是可以做的，但相对来讲会非常繁琐。

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