树链剖分学习笔记

题型

当一道题在询问两点之间修改后的权值或者是两点之间边修改后的权值。这类题目往往我们一开始就会思考用线段树来维护，但是线段树无法维护一颗树上的链，所以我们需要来将树上的链剖分下来。

轻重边剖分

将树中的边分为两部分，轻边和重边，用$size[u]$来记录以$u$为根的子树的节点个数，之后令$v$为$u$的儿子中$size$最大的一个，那么我们就可以将$u$的边分为重边和轻边了(重边就是$(u.v)$)。

之后我们就可以得到如下性质

如果$(u,v)$为轻边，那么$size[v] \leq size[u]/2$。因为如果大于的话，他就成为重边了。
从根到某一点的路径上轻边的个数不会超过$logN$。假设从$root->v$，那么$size[v]>=1$，可以递推出$size[root]>=2^k$，其中$k$为根到点进过的点数。

实现

初始化操作

首先我们定义以下几个数组

$size[v]$表示以$v$为根的子树的节点数
$dep[v]$表示$v$的深度（根的深度为1）
$top[v]$表示所在重链的顶端节点
$fa[v]$表示父亲节点，$son[v]$表示重儿子节点
$w[v]$表示与父亲的连边

然后我们使用两个dfs来把数组确定下来。

第一个dfs求出fa,dep,size,top,w。

第二个dfs

对于循环到的$v$，当$son[v]$存在的时候，也就是非叶子节点，那么$top[son[v]] = top[v]$是显而易见的。在线段树中我们规定孩子节点的重边必须在父亲节点的后面，那么$w[son[v]]=totw+1$，其中$totw$表示线段树中加入的最后一条边的位置。之后进行递归dfs(son[v]);
对于$v$的轻孩子，那么他们没有身处重链所以$top[x]=x$。那么我们为了线段树好看一点也将他加入线段树。$w[x]=totw+1$。

经过两个dfs我们把所有的数组都给他确认了。

这代码量该有多大啊，对于常年只写70行就要debug很久的我来说。

更新操作

因为我们其实也是慢慢修改路径上的边的，所以我们先求个LCA。之后更新$u,v$到祖先节点。方法意会吧，或者看代码。

查询操作

跟更新操作很像，就是在过程中不再更新，而是求值。

例题

Aragorn’s Story

+1 更新节点的时候必须在id[x]更新

+1 大于小于没弄明白，在change函数中。

+1 update的时候以为是线段树直接从左边更新到右边，其实是在那个重边更新，所以是update(val,id[x],id[t1],1,totw,1);这样的操作。

#include
using
#define
#define
#define
#define
#define
#define
void
int
a = b;
b = temp;
}
typedef
typedef
const
//head
const
int
int
int
struct
int
}G[maxn

个人鄙见：

树链剖分就是将树一部分分成区间修改，一部分分成单点修改，但是单点修改的复杂度控制在了$O(logN)$。

> Reference:
> https://blog.csdn.net/dyx404514/article/details/8718249

树链剖分学习笔记

https://www.cheasim.com/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/2018/09/29/%E6%A0%91%E9%93%BE%E5%89%96%E5%88%86%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0.html

作者
CheaSim

发布于
2018-09-29

更新于
2018-09-30

许可协议

#[acm](/tags/acm/)[树链剖分](/tags/%E6%A0%91%E9%93%BE%E5%89%96%E5%88%86/)

树链剖分学习笔记#

题型#

轻重边剖分#

实现#

初始化操作#

更新操作#

查询操作#

例题#

Aragorn’s Story#