详解树链剖分

树链剖分,顾名思义为将链剖开分成多条。

当我们想要修改树上一条路的值或求值时,我们暴力只能用一个个修改,这是非常慢的。这时,我们就要想一个办法,数据结构?但是数据结构我们都需要连续修改,可是树上路径的编号是不连续的。于是我们想了一个办法。
我们先定义
fa[x]为x的父亲
dep[x]为x的深度
size[x]为以x为根的子树的节点个数
几个名词:
1.重边(一个节点的儿子中size最大的点与这个点之间的边)
2.重儿子 x的重儿子记为son[x](一个节点重边连接的儿子)
3.轻边(一个节点除重儿子外与其他儿子链接的边)
4.轻儿子 (x除重儿子外的儿子)
5.重链(由重边连接而成的链)
6.轻链(由轻边连接而成的链)
然后我们再定义
top[x]为x所在的重链中深度最小的节点(若x不为fa[x]的重儿子则top[x]=x,即自己一个点形成一条重链)

于是我们发现重链上的点标号都是连续的。

并且一颗子树中的编号也是连续的,且子树的根的编号是最小的。

我们举个例子,在这棵树中,son[1]=2(因为size[2]比size[3]和size[4]大)。
1,2,6,9,11构成一条重链;3,7,10构成一条重链。
top[1]=top[2]=top[6]=top[9]=top[11]=1
top[3]=top[7]=top[10]=3
top[5]=5 top[4]=4 top[8]=8
然后又这样一条性质,从根到任意一节点的路径上轻链,重链的个数都不大于logN(N为节点个数)。

现在我们将一条重链上连续标号,建立新的标号(这是为了可以在数据结构中连续修改)。
我们dfs遍历,优先走重儿子,则上面那个图的新标号tid为:
tid[1]=1 tid[2]=2 tid[6]=3 tid[9]=4 tid[11]=5
tid[5]=6
tid[3]=7 tid[7]=8 tid[10]=9
tid[8]=10
tid[4]=11

我们有了新的编号,所有的准备工作都已经完成了。
令操作为修改(求值)u到v的路径。
1. 若top[u]=top[v] 则我们可以直接在线段树中修改(求值)tid[u]~tid[v](假定tid[u]<=tid[v])的区间。
2. 若top[u]!=top[v] 不妨设dep[top[u]]>dep[top[v]]则我们可以使u跳到fa[top[u]]的位子,这样我们可以使u离v更近一些,使得u和v尽快跳到一条重链上。并且由于重链的编号是连续的,所以我们只需要修改(求值)tid[top[u]]~tid[u]的区间即可。

我们举个例子:
上图中从10~11,即u=10,v=11,因为dep[top[v]]<dep[top[u]],那么我们先使u跳到fa[top[10]]=1,然后u和v就在一条重链上了(这里正好重合了),那么我们就可以直接修改了。
BZOJ1036[ZJOI2008]树的统计Count
这题是树链剖分裸题,下面给出此题代码以供参考和理解。

 

  1. hgz说道:

    有一点细节没讲清楚,线段树上的操作还要自己YY下,总的来说挺清楚的,已A了模板题 :lol:
    2460 树的统计 测试通过 Accepted 100 1192ms 10 MB C++ 5478B 2017/07/02 10:58:18

发表评论

电子邮件地址不会被公开。 必填项已用*标注