树链剖分

将树上的点按照一定方式分为许多条链,从而将在树上的区间操作转移到线性数据结构上,减少时间复杂度的同时维护许多有用的信息。

常用的剖分依据有重链剖分,实链剖分(Link-Cut Tree)等。一般称重链剖分为树链剖分。

继续阅读“树链剖分”