@[jjsnam](/user/528114) ~~众所周知~~树剖卡不满，常数小
by FiraCode @ 2023-06-18 23:29:48
@[FiraCode](/user/528430)
用了快两年倍增了因为先学的，今天被卡崩溃了，我宣布我再用倍增就倒立拉稀（
by jjsnam @ 2023-06-18 23:31:30
@[jjsnam](/user/528114) 不如 $O(n\log n)\sim O(1)$ LCA（
by StayAlone @ 2023-06-18 23:33:52
@[jjsnam](/user/528114) 倍增LCA除了写长剖我想不到任何用途，事实上
by ppip @ 2023-06-19 00:12:43
@[StayAlone](/user/409236) 不如on-o1 lca（
by UnyieldingTrilobite @ 2023-06-19 06:49:09
@[jjsnam](/user/528114) 倍增应该是 $n \log n + q\log n$ 吧，重链是 $q\log n$ 的
by Tibrella @ 2023-06-19 07:37:12
树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。树剖是$O(1)$的。
by Querainy @ 2023-06-19 08:08:04
经lxl验证，在某个分块题，树剖la用时是长剖la的1.5倍。所以真可以当$O(1)$用。但是好像比起st表树剖就菜了一点。
by Querainy @ 2023-06-19 08:09:23
@[jjsnam](/user/528114) 树剖常数 $\dfrac{1}{2}$，当然跑得快啦！
不要问我怎么知道的，已经有神证明过了。
by Link_Cut_Y @ 2023-06-19 08:11:01
@[jjsnam](/user/528114) 能否发个代码啊，can can need 倍增
by UnyieldingTrilobite @ 2023-06-19 10:21:17