长链剖分小结

概述:

参考神犇yyb的博客

问题:如何做到\(O(nlogn)-O(1)\)复杂度求解\(k\)次祖先?

常规倍增是\(O(nlogn)-O(logn)\)的,重链剖分是\(O(nlogn)-O(logn)\)的,欧拉序st表能在\(O(nlogn)-O(1)\)复杂度内求两点LCA,但并不能查出k次祖先是谁

长链剖分

方法和树剖十分类似,代码也几乎相同,但我们每次不是挑子树最大的儿子作为重链,而是挑最大深度最大的儿子作为重链

长链剖分有如下性质:

1.所有重链长度之和是\(O(n)\)级别

显然每个点最多在一条重链内

2.如果x和k次祖先y不在同一重链内,那么y点长链的链长(所在重链末尾节点到它的距离),一定大于等于k

如果小于k,那么x-y这条链更长,与长链剖分的前提——挑最大深度的儿子相悖

继续考虑怎么利用性质

这个做法需要分类讨论

在常规的重链剖分中,如果k级祖先和它在同一重链内(用深度判断\(dep[top_{x}]-dep_[x]\ge k\)),我们可以在\(O(1)\)时间找到k级祖先(维护重链剖分序,同一重链上的点一定连续)

把这个想法拓展到长链剖分,我们去掉了x与k级祖先在同一重链上的情况

现在x和k级祖先不在同一重链上

有一个想法:我们找到x点的\(r\)级祖先,使得\(r>k/2\),我们能够\(O(1)\)时间内求出x点的\(r\)级祖先z。然后考虑z的\(k-r\)级祖先,用上面的方法提到的check一下。如果不彳亍,说明z和y不在同一链内,且z的链头T深度比y大

由长链剖分性质1可知,重链长度之和一定是\(O(n)\)级别,我们对于每个链头,暴力处理出跳\([1,链长]\)长度时的祖先!!容易发现这个预处理复杂度是\(O(n)\)的

而我们找到的\(r>k/2\),利用上面预处理出的数组就可以\(O(1)\)找到y了

还剩一个问题,这个\(r\)级祖先怎么选,才能\(O(1)\)找到呢?倍增就行了!我们令r一定是2的幂次,对于询问k,我们取k的最高位\(highbit(k)\)即可

总结一下:每个点倍增预处理\(O(nlogn)\),长链剖分\(O(n)\),链头的处理\(O(n)\),每次询问\(O(1)\)

上一篇:排序--快速排序


下一篇:八大排序算法