rt,OI wiki 上说块状链表所有操作是 O(n)O(\sqrt{n})O(n) 的,但是我之前写的时候注意到:
设块长为 bbb,总操作次数为 nnn,分裂的阈值是 Θ(b)\Theta(b)Θ(b) 的话,显然总共最多只会分裂 Θ(nb)\Theta(\frac{n}{b})Θ(bn) 次,单次分裂显然也是 Θ(b)\Theta(b)Θ(b) 的,因此分裂的总复杂度为 Θ(n)\Theta(n)Θ(n) 的,最终得出因分裂产生的运算量应该是均摊 Θ(1)\Theta(1)Θ(1) 的吧?(硬说单次操作复杂度不考虑总计的话 Splay 好像还是 O(n2)O(n^2)O(n2) 呢)