树链剖分是把一棵树分割成若干条链,以便于维护信息的一种方法,其中最常用的是重链剖分(Heavy Path Decomposition,重路径分解),所以一般提到树链剖分或树剖都是指重链剖分。除此之外还有长链剖分和实链剖分等,本文暂不介绍。
本质思想是把树剖成可以用线性结构存储的结构,然后可以用数据结构维护,这样做
-
一来为树上操作节省了不少时间
比如找LCA,一次查询时间复杂度上限为 \(O(\log n)\) -
二来一些路径的操作可以转换为区间维护
最经典的就是与线段树配合产生强大的合力进行路径或子树上的修改、查询
我们定义树上一个节点的子节点中子树最大的一个为它的重子节点,其余的为轻子节点。一个节点连向其重子节点的边称为重边,连向轻子节点的边则为轻边。如果把根节点看作轻的,那么从每个轻节点出发,不断向下走重边,都对应了一条链,于是我们把树剖分成了 条链,其中 是轻节点的数量。
标签:浅谈,剖分,树剖,连向,树链,节点 From: https://www.cnblogs.com/ycw123/p/16757564.html