我写这篇文章是因为前几天看到了一个知乎问题。我看到这篇文章的第一反应就是：你这个复杂度还不如全局平衡二叉树呢，而且看起来比全局平衡二叉树难写一万倍，真是没事找事。然而转念一想：全局平衡二叉树是怎么路径修改的？我还没有仔细考虑过这个问题呢！于是就具体实现了一下。
实现完之后，我发现我是在重新造轮子，第一篇提出这个数据结构的论文就提到了做法（虽然很不清晰）。
下面讲述了路径加常数/路径求最大值的实现。之所以选择这两个操作，是因为可以标记永久化，并且自底向上实现时可以不需要栈，写起来方便很多，并且树剖和全局平衡二叉树的（我认为常数最小的）维护方法完全相同。需要标记下传的当然也可以写，就像ZKW那样写就完事了，后文不仔细描述。之所以不选择求路径和，是因为实在是不想得到“树状数组多个log照样吊锤全局平衡二叉树”这样无聊的结论。
下文中的前缀、后缀和区间，指的是二叉树的中序遍历的前缀、后缀和区间。
路径查询
一条路径，可以拆成：$O(\log{N})$棵auxiliary tree的一段前缀和最多$1$棵auxiliary tree的一个区间。这和树剖是完全一样的（毕竟剖分方法完全相同）。由于在一棵BST上获取区间$[l,r]$相关信息的复杂度是$O(dep_l+dep_r)$，根据全局平衡二叉树一个log复杂度的证明，可以轻松看出来复杂度也是一个log的（复杂度$\le$对于两个端点和LCA，分别做三次到根查询的复杂度）。但是这里实现的时候，我把询问前缀和询问区间的函数分开处理了，因为否则常数要乘$2$的。
询问前缀的方法太简单了，就跳过了。只详细描述询问区间。可以看成在BST上求LCA的过程，论文里也提到了。统计答案就接近于ZKW区间询问的写法，只不过由于内部节点上也有值，实际上烦了很多。分成三段：
- 不断把深度较深的点往上跳，直到两个端点深度一样。一边跳一边统计答案；
- 两个点一起跳，直到跳到LCA。一边跳一边同时统计两边的答案；
- 从LCA跳到当前二叉树的根。一边跳一边考虑当前节点的标记。
当然也可以有简单很多的递归实现。只不过常数如何我就不敢保证了（我没试过）。
路径修改
具体方法本来应该和路径查询完全相同的，只不过碰巧我举的这个例子的修改具有可减性，就不需要写区间修改的函数了，只需要前缀修改，所以代码简单很多。区间修改和区间查询是差不多的。
前缀查询/修改的方法：不断往根跳，如果上一个点是当前点的右儿子，更新左子树和自身的信息，否则只要考虑自己的标记。不要忘了对于空节点是不需也不能修改的。
口胡：对于子树修改/查询的一些思考
这个我没有实现，因为举的例子不太适合。如果要子树查询，必须要支持$O(1)$修改当前重链根部对于父亲重链的贡献。动态dp可以使用全局平衡二叉树优化，正是因为这个修改可以在$O(1)$时间内完成。然而取$\max$的贡献就难以删除了，（见识粗浅的我觉得）必须要带log。
问题来了：为什么可以把用std::multiset之类的东西维护max卡到两个log？
这个数据不太平凡，但还是很好构造的（我不清楚是否有更简单的构造）：
- 先用$O(\sqrt{n})$个点构成一棵满二叉树；
- 每个点挂上$O(\sqrt{n})$个儿子
但是如果支持$O(1)$的去除贡献呢？那么带路径修改的查询一个点子树的信息，只需要询问一棵auxiliary tree的一个后缀就可以了。和前缀路径查询是对称的。只不过路径修改时需要像动态dp一样一路更新到整棵树的根节点。复杂度不变。
子树修改？首先下传tag是肯定不太行的。因为暴力下传复杂度是错的，很可能要使用某种高级数据结构维护一个点的所有轻儿子才能正常的下传tag。这样复杂度也要添log了。如果标记永久化，那么和子树查询一样做。复杂度不变，只不过需要分开来记录两个不同的tag（路径修改和子树修改），常数可能会大增。
再次声明我没写过，这些都是口胡的，不保证可以实践。
与树剖和LCT的比较
我写了两个树剖的实现。都是使用标记永久化的ZKW线段树维护每条重链的，唯一的不同是：hld_naive把所有的重链记在同一棵线段树里，而hld每条重链单独开一棵线段树。
LCT就没有什么优化的空间了：我从来没听说过标记永久化的LCT。不知道是否可以做到不换根、不维护和下传区间翻转标记。
树的点数都是$10^6$，总操作次数都是$3\times 10^6$。读入输出、存树边等等无关过程均未使用任何优化（scanf读入，basic_string存边）。
下面有两张表格。第一张是对于不同数据，用时的表格；第二张是对于不同数据，操作次数的表格。对于树剖和全局平衡二叉树，”操作次数”均定义为访问数据结构节点的次数；LCT的“操作次数”是rotate的调用次数。
| 用时 | hld | hld_naive | lct | gbst |
|---|---|---|---|---|
| chain | 1.872 | 1.725 | 7.323 | 3.597 |
| chain_like | 2.964 | 3.095 | 7.147 | 3.881 |
| complete_binary | 4.444 | 6.604 | 6.249 | 3.097 |
| hld_killer | 5.340 | 5.870 | 6.514 | 3.827 |
| random | 3.523 | 4.650 | 4.912 | 3.136 |
| star | 2.005 | 1.945 | 1.381 | 1.268 |
| 操作次数 | hld | hld_naive | lct | gbst |
|---|---|---|---|---|
| chain | $1.14\times 10^8$ | $1.14\times 10^8$ | $1.58\times 10^8$ | $1.11\times 10^8$ |
| chain_like | $1.36\times 10^8$ | $2.67\times 10^8$ | $1.58\times 10^8$ | $1.05\times 10^8$ |
| complete_binary | $2.77\times 10^8$ | $1.18\times 10^9$ | $1.66\times 10^8$ | $1.03\times 10^8$ |
| hld_killer | $5.28\times 10^8$ | $9.86\times 10^8$ | $1.58\times 10^8$ | $1.08\times 10^8$ |
| random | $1.74\times 10^8$ | $7.11\times 10^8$ | $1.08\times 10^8$ | $6.09\times 10^7$ |
| star | $2.70\times 10^7$ | $1.95\times 10^8$ | $1.20\times 10^7$ | $9.00\times 10^6$ |
编译器均为G++ 10，编译参数均为-Ofast -march=native，运行时均使用了ulimit -s 262144，时间是指real time。加粗的是这一项数据中最优的数据结构。
数据说明（$\rm{rand}(x)$表示$[1,x]$区间中的随机整数），询问均为随机生成：
- chain：从$1$到$n$的一条链
- chain_like：$fa_i=\max{(1,i-\rm{rand}(10))}$
- complete_binary：完全二叉树
- hld_killer：链式堆，每条链长度为$100$(这里没有用$\sqrt{n}$，$100$是三分出来的最慢值)
- random：$fa_i=\rm{rand}(i-1)$
- star：菊花树
可以看到，全局平衡二叉树的总体表现远好于复杂度相同的LCT（LCT甚至比朴素的树剖还要慢，除了菊花图）；对于随机数据和完全二叉树，由于重链多而短，hld_naive远优于hld。全局平衡二叉树除非树很接近链，表现都好于优化过的树剖。
操作次数，反映的就是数据结构的纯理论复杂度和常数，所以不会受到各种玄学底层常数问题的影响。所以得到了全局平衡二叉树略小于LCT，LCT小于每条重链单独开线段树的树剖，优化过的树剖又远小于朴素树剖的预料之中的结果。
代码难度：LCT(56行)$<$朴素的树剖(77行)$<$优化的树剖(80行)$<$全局平衡二叉树(95行)
代码和链式堆的gen全部放在我的代码仓库里了。
