欢迎转载,转载请注明来自 bestsort的博客 并保留该超链接
算了算自己大大小小也看了不下十几篇关于树链剖分的博客了吧,但是总感觉差强人意,基本上都是一上来就告诉读者我们来先背几个概念,然后就是 轻儿子重儿子重边重链 什么的一股脑全堆上来.但是个人感觉这种方式对初学者并不友好! 笔者不才,打算自己根据对树链剖分的理解重新写一篇真正适合入门的详解
这里,笔者打算以 What-How-Why(黄金圈法则) 的方式进行讲解.先知道树链剖分是什么,它有什么用,再去了解它怎么实现,具体原理是什么
What
树链剖分是什么
树链剖分就是将树分割成多条链,然后利用数据结构(线段树、树状数组等)来维护这些链。
实际上,这些链是一条条平躺着放在数组里面的
How
映射的规则
上文中说过树链剖分是把树分割成多条链,并将其映射到一维数组
当然分割是要讲道理滴!自然要遵循某些规则
这里的规则很简单,那就是
在一维区间中,对于任意树上结点 x, 则 x 的所有子孙结点都在以 x 为起点的一段连续区间内(当然,树链还有一些其他的约束条件,我们放到后面再说)
很难理解?
比如说 我有下图这颗树
)
我们可以构造出下面这些区间,都满足上面的规则.(注意是任意结点 x 都满足规则)
1 | #分别对应 [ABDCEF],[BD],[CEF] |
也就是说映射到最后的结果是:对于任意节点 x, x 和它的子树在区间内一定连续的
对于这个规则,我们不难想到,其实就是一个 DFS
的事情(想不通的可以看一下二叉树的前中后序遍历出来的结果).
Ok, 现在我们知道了,要用 DFS
将树映射成一维区间.可是遍历顺序有没有影响?
有的!
而正是因为分割规则的不同,才有长链剖分和重链剖分这两种说法,本文只讲重链剖分.当然不是说长链剖分就没用,两者在不同的场合都有各自的优势,这里不赘述了
回到上文,遍历顺序
是对最终的复杂度有影响的.这里举一个具体的例子,如下图:
有点懒,不想写了….具体的待补充
题目链接 先放代码占坑,过几天有空再写
1 |
|