关于长链剖分
查看原帖
关于长链剖分
399475
_XHY20180718_楼主2023/10/4 10:25

朴素长链剖分求LCA是否可以被卡到 O(n)O(\sqrt n)?

不用倍增,就跟重链剖分一样的求LCA。

卡的方法就是先造一棵链(假设每个节点都为右儿子),然后每个节点往左边延伸至比这条链长。

这一棵链理论上可以被卡到 O(n)O(\sqrt n) 个。

如果会被卡,有没有什么优化方法。

2023/10/4 10:25
加载中...