@[Yahbim](/user/372708)
1. 复杂度是对的。考虑每一个点的贡献次数。它被访问的次数就是它在所在重链的二叉树上的深度，而所有点深度和是 $O(n\log n)$ 的。
by Kubic @ 2021-12-23 20:08:59
@[Yahbim](/user/372708) 复杂度是对的。首先在任意链上查询等价于在父链上查询。我们需要证明的就是分裂到的点数量是 $O(logn)$ 的。我们把每一次分裂当做往下走一步。如果它走了一条轻边，那么 size 会至少 $\div 2$；如果它在重链的二叉树上往某个儿子走了一步，那么 size 也会至少 $\div 2$。综上，每次跳的次数都是 $O(\log n)$ 的。
by Kubic @ 2021-12-23 20:16:06
@[Kubic](/user/119621) 知道了，谢谢大佬！
by Yahbim @ 2021-12-23 20:46:15