目前搜索引擎上找到的与树链剖分相关内容大多含糊不清, 略去了最基本的原理而从 “轻重剖分” 开始讲起. 找了许久终于发现 陈乐群老师 的一句讲解最和心意.
“个人认为，其实树链剖分并不是一个复杂的算法或者数据结构，只是能把一棵树拆成链来处理而已，换一种说法，树链剖分只是xxx数据结构/算法在树上的推广，或者说，树链剖分只是把树hash到了几段连续的区间上。”
简单来说, 就是把一颗树按照某种遍历方式, 将出现概率比较大的边按照需要重新排序储存.
如 最常见的线段树套轻重边剖分, 所谓轻重其实是指代 占比轻重. 占比重更大的边在所有路径集合中出现的概率更高. 对于每个非叶子节点引出且只引出一条占比最大的边, 即: 父节点指向儿子树中节点最多的儿子的边. 相连通的重边集合称之为重链, 不是重边的边称之为轻边.
这样, 一个给定的路径 $(u, v)$ 就可以被划分为几段分别经过轻边和重链的路径了. 可以证明, 在路径 $(u, v)$ 中, 最多经过数量为 $log_2(n)$ 条轻边. 那么将所有重边放到一个数据结构之中维护, 进而统一修改, 即可达到目的. 如放置于线段树中, 则可以将 “查询/修改” 两点之间经过所有的 边/点 权值映射到 “查询/修改” 线段树区间权值中.
树上倍增
树上倍增利用二进制拆分思想, 设深度为 $k$, 则存储下每个点的 $2^i, [i∈(0, log_2(k))]$ 辈父节点的编号. 那么即可以在 $log_2(k)$ 的时间内计算出树上任意两点之间的最深公共父节点.
查询节点 $x, y$ 的LCA:
1. 不妨设 $y$ 更深, 即 $d(y) > d(x)$ .
2. 利用二进制拆分, 将 $y$ 向上调整到和 $x$ 同一深度.
- 依次尝试 $y$ 的 $2^{log_2(k)}, 2^{log_2(k)-1},\,…\,, 2^1, 2^0$ 辈父节点
- 检查每个父节点是否比 $x$ 更深,
- 若是, 则将 $y$ 调整到该父节点并继续检查.
3. 利用二进制拆分, 判断 $x, y$ 向上调整到第几层的时候相遇.
- 与操作2类似, 依次尝试 $y$ 的 $2^{log_2(k)}, 2^{log_2(k)-1},\,…\,, 2^1, 2^0$ 辈父节点
- 检查每个节点是否一致.
- 若不一致, 将其调整至该节点并继续检查.
- 直到无法调整为止, 此时应有 $x’,\,y’$ 的父节点为LCA
4. 可以另行记录每个点到 $2^{log_2(k)}, 2^{log_2(k)-1},\,…\,, 2^1, 2^0$ 辈父节点的距离, 在计算LCA的同时求出两点路径长.
- update: 显然, 更方便的方法是用 O(n) 的时间处理出每一个点的深度, 则有 $path(x, y) = d[x] + d[y] - 2 * d[LCA(x, y)]$.
树上差分
利用两端点的标记(+1)以及两点LCA的标记(-1, -2), 可以确定一条路径. 利用对每个节点的子树标记求和可以得到子树内路径数量.
2018-03-25
