算法小站
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
登录
注册
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
wiki 主题
算法基础
搜索
数据结构
线段树
线段树单点修改
线段树区间修改
可持久化线段树
树链剖分
平衡树
FHQ-Treap
字符串
数学
图论
图的连通性
有向图的强连通分量
无向图的割点割边和双连通分量
动态规划
计算几何
杂项
启发式合并
高精度
主题名称
是否为父主题
是否为其添加wiki文章
取 消
确 定
选择主题
修改主题名称
修改父主题
修改wiki文章
取 消
删 除
修 改
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
数据结构
线段树
线段树单点修改
线段树区间修改
可持久化线段树
树链剖分
平衡树
FHQ-Treap
[[ item.c ]]
1
1
树链剖分
## 树链剖分的概念 **树链剖分** 把树分成若干条链,一般只考虑从根往下的链(树链一般不拐弯),保证每个点**只在一条链上** 换句话说,对于每个节点,都选一个儿子相连,分为**长链剖分**和**重链剖分** **长链剖分**,选择一个儿子相连,使得这个儿子对应的子树中,有一个**深度最大的节点** **重链剖分**,选择**`size`最大**的子树相连 一般用的比较多的是**重链剖分** 对于根节点`u`,找**`size`最大的子树**(子树对应的**儿子**是`v`),那么$$(u, v)$$ 是重边 和其他儿子相连的边都是轻边,同样`v`是**重儿子**,其他儿子是轻儿子 ![](/media/content_img/heavy-light-decomposition-01.jpg) > 树链剖分能解决什么问题 考虑一个节点`u`往上走到`root`,经过**轻边**,子树大小翻倍 > 证明,如果路径是轻边,假设当前经过的节点是`u`,那么`u`是轻儿子 同时,`u`肯定有一个兄弟节点`v`是**重儿子**,满足`size(v) >= size(u)` 沿着`u`再往上找到`u`的父亲`w`,那么 `size(w) = size(u) + size(v)` 也就是说 `size(w) >= 2*size(u)` 沿着轻边走,最多只会有$$O(\log n)$$条轻边 对于任意两个点`u, v`的路径,轻边数量 $$\leqslant O(\log n)$$ 考虑`u, v`的路径,它由**若干段重边**和若干条轻边相连而成,由于轻边数量最多是$$O(\log n)$$ 由此重边最多有$$O(\log n)$$段(当然每一段也可能有很多条重边) 只需要用$$O(\log n)$$复杂度内,去维护**重链信息**,这样整个问题复杂度是$$O(\log ^ 2 n)$$的 **树链剖分大致流程** * 第一遍 `dfs`,记录每个节点的父亲,深度,子树大小,重儿子节点编号 * 第二遍 `dfs`,求出每个点的**重链优先**`dfs`序,重链上的链头的元素 > 重链上的链头元素,类似于链的顶端(靠近`root`的顶端) 重链优先,如果一个点有重儿子的话,要先`dfs`重儿子,链头不变 (如果是轻儿子,链头就是轻儿子本身) ```bash const int maxn = 1e5 + 10; vector<int> dep(maxn, 0), pa(maxn, 0), hs(maxn, 0), sz(maxn, 0); vector<vector<int> > G(maxn); // 第一遍dfs,求出深度,子树大小,重儿子,父亲 function<void(int, int)> dfs1 = [](int u, int fa) -> void { dep[u] = dep[fa] + 1; sz[u] = 1; pa[u] = fa; hs[u] = -1; for (auto v : G[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; if (hs[u] == 1 || sz[v] > sz[hs[u]]) { hs[u] = v; } } }; // 第二遍dfs,求出dfs序,重链上的链头元素 vector<int> l(maxn, 0), r(maxn, 0), top(maxn, 0), id(maxn, 0); int tot = 0; function<void(int, int)> dfs2 = [](int u, int t) -> void { top[u] = t; l[u] = ++tot, id[tot] = u; if (hs[u] != -1) { dfs2(hs[u], t); } for (auto v : G[u]) { if (v != pa[u] && v != hs[u]) { dfs2(v, v); } } r[u] = tot; }; ``` ## 树链剖分求 LCA **问题描述** 给定$$n$$个节点的树,有$$m$$个询问,对于每组询问,给定$$u, v$$ 输出$$u, v$$最近公共祖先的编号 **算法分析** 考虑对于点$$u$$不断**往上跳**,如果是重链跳到**链头**,否则就跳一条**轻边**,即 $$u \to \text{top}(u) \to \text{fa(top}(u))$$ 这样最终两个点都会跳到**一条链**上,LCA 就是**深度更浅**的点 > 那么问题是,应该跳哪一个点呢? 其实,我们可以看成每一次只跳一步,是重边就跳`u -> top(u)`,是轻边就跳 `u -> fa(u)` 每一次都要跳**链头深度更深的点** > 这很好理解,将重边看作是一条边,这样每次我们只往上跳一步 假设跳的过程是`u -> next(u)`,一定是选择 `next(u)`更深的往上跳 > 如果**链头**`top(u)`深度一样呢?那么 `top(u) -> fa( top(u) )` 一定是**轻边** 跳哪个点其实都一样,都能跳到一起 ```bash LCA(u, v): while top(u) != top(v): if dep(top(u)) < dep(top(v)): v = fa( top(v) ) else: u = fa( top(u) ) if dep(u) < dep(v) return u else return v ``` ## 路径修改和查询 **问题描述** 给定$$n$$个节点,每个节点有一个权值$$w$$,现在有一些操作 * `1 u t` 将`u`点权值改成`t` * `2 u v` 查询`u->v` 路径上的最大权值 * `3 u v` 询问从`u->v`路径上的节点权值和,包括`u`和`v` **算法分析** > 注意到两个点之间的路径,对应$$O(\log)$$段重链,如果对每段重链开一个线段树 就对应每一个线段树的区间查询 注意到之前是按**重链优先**得到的`dfs`序,每一段重链的编号都是连续的 也就是说,重链对应**连续的一段区间** 如果对`dfs`序建线段树,**一段重链**就对应`dfs`序中的一段区间,这样就可以修改和查询了 > 问题是,怎么找到`u->v`对应的**重链路径** 类似于之前求`LCA`的过程,选链头更深的点往上跳,考虑 $$u \to \text{top}(u)$$ `top(u) -> u` 对应`dfs`序中 `[l(top[u]), ..., l(u)]` 这一段区间 每跳一步就用这一段区间的信息来更新答案 两个点跳到一条链上的时候,再用`[l(u), l(v)]`这一段区间更新答案 **算法实现** * 树链剖分求出重链优先的`dfs`序,用`dfn`记录 * 根据`dfn`数组建立线段树,那么我们有 - 单点修改 `u->val`,线段树上执行`tr.set(l[u]-1, S{val, val})` (减`1`是因为线段树下标从`0`开始) - 区间查询,类似`LCA`的过程 ```bash while top[u] != top[v]: if dep[ top[u] ] > dep[ top[v] ]: ans = op( ans, [l[top[u]]-1, l[u]) ), u->pa[top[u]] else: ans = op( ans, [l[top[v]]-1, l[v])] ), v->pa[top[v]] if dep[u] > dep[v]: ans = op( ans, [l[v]-1, l[u]) ) else: ans = op( ans, [l[u]-1, l(v)) ) ``` **[SDOI2011 染色](https://ac.nowcoder.com/acm/problem/50487)** **问题描述** 给定$$n$$个点的树,有以下操作 * 将 `a->b` 路径上的所有节点都染上颜色 * 询问`a->b`路径上的颜色段数量,比如`112221`有`3`段,`[11], [222], [1]` **算法分析** 树链剖分的框架大致不变,问题是,如何统计信息? 线段树维护信息 `{ lc, rc, cnt }`,其中`lc, rc`分别表示左右端点的颜色 `cnt` 维护区间内**颜色的段数**,特别地,如果颜色都相同,`cnt = 0` > 线段树如何合并信息? `S op(S a, S b)` 函数返回 `S{a.lc, b.rc, a.cnt+b.cnt+(a.rc != b.lc)}` **特别地**,如果一段内颜色**都相同**,区间的`cnt`值设为`0`(这样边界情况简单很多) (这样最后统计答案的时候,一整个序列的颜色段数要记得`+1`) `F`和`S mapping(F, S)`如何定义? `F`涉及区间修改,可以定义为二元组`(mul, add)`,改成 `col`颜色对应`(0, col)` 这样单位变换也容易定义,`ID = (1, 0)` `S mapping(F f, S x)`,映射操作,实际上修改后的颜色是 `{lc*f.mul+f.add, rc*f.mul+f.add, 0}` `int comp(int f, int g)`,即作复合变换$$f(g(S))$$,`(fmul*gmul, fmul*gadd+fadd)` > 树链剖分如何维护信息 * 路径 `u->v` 的修改操作,套用树链剖分的框架 沿着 `u -> fa( top(u) )` 往上跳的时候,线段树修改区间 `[ l(top(u))-1, l(u) )` (因为线段树维护的下标从`1`开始) 当 `u, v` 跳到同一条链上的时候,线段树修改区间 `[ l(u)-1, l(v) )` * 查询操作,注意**考虑顺序**,`ans`初始化为`{ 0, 0, -1 }` 这是因为`0`是哨兵,之前的操作**没有**`0`这个颜色,所以`ans`和颜色相同的一段并起来 会让`cnt += 1`,新的段的`cnt`恰好是`0`,很好地解决了边界问题 * 查询操作,用`ansu, ansv`分别表示`u, v`到`LCA`的两条链,需要分别计算,最后合并 `u->top(u)`这条链的信息,和`dfs`序是**反的**,而相应的`lc, rc`也应该反过来 * 统计的时候,`v->top(v)`往上跳,对应查询`dfs`序的`[l(top(v))-1, l(v))` 这个顺序刚好和`u->v`的路径**方向一致**,因为是往上跳,相当于在`ansv`的**前面接了一段** 所以`ansv = op( [l(top(v))-1, l(v)), ansv )` 而 `u->top(u)` ,`[l(top(u))-1, l(u))`方向和路径**方向相反** 统计`ansu`的时候可以像`ansv`一样做,只不过`ansu`中的信息和实际的是**相反的** 合并`ansu, ansv`的时候,对于`ansu`的`lc, rc`要取反 返回`{ ansu.cnt+ansv.cnt+(ansu.lc != ansv.lc)+1 }` (`+1`是因为如果一整段颜色都相同,我们统计时候是按`0`统计的,实际上应该是`1`) > 记一下代码中容易错的地方 `S mapping(F f, S x)` 容易写错,当`f.mul == 0`的时候,是修改操作,新的`cnt = 0` 如果`f.mul == 1`,那么表示单位变换,要令`cnt = x.cnt` 返回 `{ lc = f.mul*x.lc + f.add, rc = f.mul*x.rc + f.add, cnt }` ## 子树的修改和查询 **[软件包管理器 NOI2015](https://ac.nowcoder.com/acm/problem/17882)** **问题描述** 给定一个`0`号点为根的**有跟树**,一开始整棵树中所有点的权值都是`0`,给定两种操作 * `install x`,把`x->root`路径上的所有点都从`0`变成`1` * `uninstall x`,把`x`及其子树中的所有点都从`1`变成`0` 每种操作,输出有多少个点发生了变化?即从`0`变成`1`或者从`1`变成`0` 原来是`0`的再设为`0`,被视为不变 **算法分析** 考虑树链剖分,对于`uninstall x`操作,只需要找到`x`所在的子树即可 这就对应`dfs`序中`[l(x), r(x)]`,在`dfs`序线段树中执行区间修改,修改为`0` `install x` 操作呢?这时候不需要两个点一起跳了,只需要令 `x -> pa[ top[x] ]` 直到跳到根节点,跳的过程中执行区间修改 `[ l(top[x]), l(x) ]`,将区间全部改成`1` > 线段树如何维护信息? 线段树需要维护`{cnt, sz}`,其中`cnt`表示区间中`1`的个数,`sz`表示区间中节点的个数 映射算子`F`定义为`F{ mul, add }` 如果将区间值全部设为`1`,`cnt = cnt*0 + sz`,此时`F{0, sz}` 如果将区间值全部设为`0`,`cnt = cnt*0 + 0`,此时`F{0, 0}` 单位变换是`F{1, 0}` > 如何统计信息 只需要记一下`last`,表示上一次**整棵树**有多少个值为`1`的点 然后执行线段树**根节点查询**,当前整棵树有`res = all_prod().cnt`个节点 那么 $$|last - res|$$ 就是答案,然后更新`last = res`继续
看完文章有啥想法
发布评论
目录
[[ item.c ]]
671 人参与,0 条评论