2025年树链剖分(轻重链剖分)

科技前沿 • 2025-01-12 11:00 • 阅读 86

大家好，我是讯享网，很高兴认识大家。

树链剖分,是一种将树剖分为链,在链上进行各种操作以达到目的的算法.树链剖分(轻重链剖分)可以解决lca(最近公共祖先),树上操作(对树上两点及经过的路的权值进行求和,修改等操作)等一类操作.对于这些问题建议逐个进行理解.

在理解问题之前,要对树链剖分的某些概念有了解:

1.对于每个点,存在一个size来记录它的子树大小,对于每个父节点,它的子节点的子树的大小(即子树上点的个数)size值最大的就是它的重儿子,其余的点都是它的轻儿子.每两个重儿子间靠重边相连,连接每个重儿子的边连在一起叫做重链.对于一个有了重儿子的节点来说,其余的可遍历的点(除了父节点)都是它的轻儿子,它与轻儿子之间的连线就叫轻边.如果某个父节点没有子节点,那么它本身就可以看做一条重链.如图:

讯享网

那么图中的重链就是:

1. 1->4->5->7

2. 2->3

3. 6

然后还要引入深度deep,父节点fa,top节点,还有一个记录重儿子的son,包括上面的size,五个数组.deep,顾名思义,就是求当前节点在树上的深度(从根开始往下遍历的深度),上图根节点1的深度是1,那么3的深度就是3,7的深度就是4.fa节点,是单向的关系,fa节点就是当前节点的上一层节点(接近根节点的那层),例如4的fa节点就是1.top节点记录的是当前节点所在的重链的最上方的节点,在2->3这条重链上,每个节点的top节点都是2.重儿子son的含义就是当前节点往树的下方遍历(不会去遍历父节点)size的值最大的,也就是它的重儿子son.

这就是解决一些问题基本概念了.

LCA(最近公共祖先)

lca有两种求法,一种是倍增算法,还有一种就是树链剖分(当然,没有完全利用树链剖分).

首先先理解一下lca的基本思路:

要是要找2和6的最近公共祖先,所谓找最近公共祖先,就是将这两个点向上搜索,搜索到的第一点,在此点两条路相遇,并且保证走的路最少.一开始我就想用dfs直接搜索,但是由于没有预处理父节点这些,就很容易搜爆.树链剖分的思路就是先判断两点的深度是否相等,不相等就将深度深的那个点往上寻找父亲节点,直到两者在同一深度上,这一步是因为有一种情况是两者在一条重链上,从更深这样一直找就可以直接找到它的祖先就是浅一点的那个点.由此两者最近公共祖先就是较浅的那个点,但是也有两点不在一条重链的情况.当两者不在一条重链,我们仍然按照之前的做法,当两者在同一平面后,在将两者一起向上搜索父节点,直到两者重合,找到的该点就是他们的最近公共祖先.

下面结合一道杭电oj题目来理解lca;

How far away ？

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 88 Accepted Submission(s): 37

Problem Description

2025年树链剖分(轻重链剖分)

How far away ？

相关推荐