【模板】动态树链剖分
由于会不断插入新节点，所以无法做到保证树链剖分的结果最优。
这时有两个不使用点分树的思路。
一个是定义平衡因子$\alpha$，按照重量平衡（替罪羊树）的思想不断重构树剖，可以证得单次操作的摊还复杂度最坏情况下为$O(\frac{\alpha}{2\alpha-1}log_{\frac{1}{\alpha}}n)$。注意，这是插入一个节点需要的对点操作的期望复杂度，而树链剖分上的单点修改复杂度是$O(logn)$的，所以整体复杂度为两个log级别。经过计算，$\alpha$在取0.658时期望操作个数在$n=100000$时有最小$84$。
另一个做法就是将维护树链剖分的数据结构由线段树换成$FHQ treap$，这样就可以做到快速改换树剖的某一部分，但这样写还是会出现一些问题，比方说判断一个点在哪一条重链上就非常麻烦（但并非不能处理）。
这时，就会发现重链剖分的局限性：不便于修改。或者说，每次选择子树大小最大的子树确实能达到$O(logn)$的渐进复杂度下限，但是这并非是最优的树剖方法。举个例子，一坨菊花和一根没菊花那么大的链，重链剖分时会选择菊花，但是很明显选择链更优。
对于树剖的优秀程度有两种判断方式，一种方式是计算所有点到根要跳的距离和，另一种是所有点到根的距离的最大值。通常讨论最坏情况下的复杂度，所以选择第二种方式来评判树剖的优秀程度。
具体来说，定义一个节点的秩为子树内一个节点通过跳重链的方式跳到当前节点的次数。树链剖分的时候选择儿子中秩最大的一个作为重儿子，可以证明一个节点的秩为儿子中秩最大的节点的秩和次大的秩+1的最大值。换言之，至少要存在一个大小不小于当前子树的兄弟节点才能使当前节点向上的秩+1，这一点可以直接参考安置合并并查集的复杂的证明，最坏复杂度是$O(logn)$的，而且大概率跑不满。
而且与维护儿子重量平衡不同，维护儿子重量平衡的时候需要一直更新到根，因为可能在深度较大的节点处重量平衡但是在深度较浅的节点处重量不平衡。但是如果使用维护秩的方式来更新重儿子的话，一旦无法更新当前链的秩，也一定无法更新深度更浅的链。
因为整棵树的秩之和有一个上界为$\sum log(siz[u])=O(nlogn)$，所以插入一个节点的摊还复杂度有一上界为$O(logn)$。实际上，还可以使用构造法严格证明这一上界不仅是摊还的复杂度，更是单次操作的最坏复杂度。
但是还没完，修改不仅仅涉及到插入，还有删除操作，即将链的一段切割下来，在续接一段上去。同样，这里也有两种做法。
第一种非常的暴力，就是上面的用$FHQ treap$来做，实际上还有一些小优化，比方说将$treap$的随机权值设为深度的lowbit之类的。这要做总共需要$O(nlogn)$次操作，总复杂度$O(nlog^2n)$。
第二种更加暴力，就是单纯的暴力修改。当然，这样做的前提还是得基于复杂度分析。定义一个势函数为每个节点要成为重儿子要达到的秩的大小，同一条链的势相同并为为链顶的势。很显然的是整棵树每个节点的势函数值之和有上界$O(nlogn)$。每当一条链被断开，那么断开的这部分链的势能每个都+1，与操作次数线性相关。即单点修改次数最多为势能总数，即$O(nlogn)$。而单点修改的复杂度为$O(logn)$，所以总复杂度为$O(nlog^2n)$。
那么就可以大力进行修改了，信息也可以直接使用主席树来维护，时空复杂度$O(nlog^2n)$。