Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

从零开始的树链剖分——浅谈树链剖分的原理和实现

写作背景(雾

树链剖分是传说中高级数据结构
一直用倍增写LCA的我一直拖着没有学树链剖分
直到我发现树链剖分辣么有用

先给出例题

传送门
看看题

小问答

Q:什么是树链剖分
A:树链剖分就是说把一棵树人为地分成很多条链
然后把树上面的操作变成链上面的操作
这样大大减小复杂度

一些小概念

重结点:子树结点数目最多的结点;
轻节点:父亲节点中除了重结点以外的结点;
重边:父亲结点和重结点连成的边;
轻边:父亲节点和轻节点连成的边;
重链:由多条重边连接而成的路径;
轻链:由多条轻边连接而成的路径;

比如在上面这棵特别丑的树上面
所有带有红道的都是重链
所有带有红点的是任意一条链(轻重都可以)的开始
重链包括 1->12 3->10 7->11
在进行树上面的操作的时候
每条边要有执行的顺序
大概就是一个标号的操作
为了便于我们维护一条完整的链
我们最好是把这条链上面的所有边的标号连到一起
这样的话dfs序自然是最好了
这个标号也可以理解为这条边连的两个点中深度大的那个的dfs序

就像这样
这样的好处在于每条链的标号都形成了一条区间
可以套数据结构了
比如那道例题就需要套线段树
然后在写程序的时候
需要用到一些变量
下面列出的是数组名称加上意义
son[i]->表示第i个节点的重儿子
deep[i]->表示第i个节点的深度
fa[i]->表示第i个节点的爸爸
tot[i]->表示第i个节点的子树大小
top[i]->i这个节点所在链的顶端的节点
除此之外 我们还有一些显然的性质
1.如果u->v是一条轻链 那么size(v)<size(u)/2
这个正确性是显然的 如果不是这样的话这就是一条重链了
2.从根结点到任意结点的路所经过的轻重链的个数必定都小与O(logn);
下面正式开始了
第一步是一个dfs
用来找出每个节点的重儿子 父亲节点 深度

第二步是另外一个dfs
第二次DFS的时候则可以将各个重结点连接成重链,轻节点连接成轻链,并且将重链(其实就是一段区间)用数据结构(一般是树状数组或线段树)来进行维护,并且为每个节点进行编号,其实就是DFS在执行时的顺序(tid数组),以及当前节点所在链的起点(top数组),还有当前节点在树中的位置(rank数组)。

比较重要的两次dfs就结束了

而修改和查询操作原理是类似的,以查询操作为例,其实就是个LCA,不过这里使用了top来进行加速,因为top可以直接跳转到该重链的起始结点,轻链没有起始结点之说,他们的top就是自己。需要注意的是,每次循环只能跳一次,并且让结点深的那个来跳到top的位置,避免两个一起跳从而插肩而过。
这种操作一般要联系线段树或者树状数组这种数据结构了
所以就不给代码了

首先是我前面提到的
链剖能够用来求lca
理解的话大概就是加速了倍增的速度
倍增一次是跳了2^i
链剖的话一次能跳一整条链
相对来讲更加的优秀
代码跟倍增类似
就是当两个点不在同一条链上面的时候
所在链深度大的往上面跳
在一条链的时候
直接找深度小的那个就是lca了
代码如下

接下来大家去看看那道题
这里要补充的是
前面给出求lca的代码就是因为在链剖问题上面
lca是必备操作
要想对树上的一些东西进行操作
到一条链上面是必须的
这样的话就用到了求lca的操作

代码

这个时候跑来另外一道裸题
传送门
题解链接在下面
传送门

Add a Comment

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

隐藏