树链剖分学习笔记
Part -1 引子 & 概念
我们通常所讲的树链剖分其实是轻重链f剖分。
树剖是什么？是一种让你的码量不得不超过 2.4kb 的可以维护一棵树路径的数据结构。
首先，如何维护一个数列的区间和或者是区间修改使两者的时间复杂度为 (O(log_2 n)) 呢？
显然，线段树可以轻松维护。
但是如果我们把这个问题挪到树上；
然后，如何在一棵树上维护 (u) 到 (v) 两点简单路径上的点权和或是修改点权使他们的时间复杂度仍然为 (O(log_2n)) 呢？
那就把出题人暴打一顿
线段树是维护不了的，那么我们该怎么办才能使两个操作的时间复杂度为 (O(log n)) 呢？
（灵光乍现）我们可以给每个节点编个号，割成若干个不相交的编号连续的链，然后用线段树一条一条维护。这样，将点 (u) 到 (v) 的简单路径就可以变成若干条链，每条链用 (O(log_2 n)) 维护，总时间复杂度也是 (O(log_2 n))。
但是——
怎么编号？怎么割成链？
轻重链剖分就是用一种方法编号和割成链从而达到使维护树两点路径 (O(log_2 n)) 的东西。
Part 0 定义
下面，我们以板子来扯树链剖分。
首先，在学树链剖分之前，我们要明白一些定义：
| 名字 | 意思 | 备注 |
|---|---|---|
| 重儿子（(son)） | 父亲节点上子树大小最大的节点 | |
| 轻儿子 | 不是重儿子的节点 | |
| 轻边 | 任意节点到轻儿子的边 | |
| 重边 | 任意节点到重儿子的边 | |
| 重链 | 若干收尾相衔接的重边 | 顶端必为轻儿子，落单的轻儿子也是重链 |
如果是这样，我们就会发现，一棵树必定会被拆成若干条重链，Why？
首先，只要一个节点不是根或是叶子，肯定是有重儿子的，那么剩下的点是轻儿子，会被算成重链。
那么他们相不相交呢？
每一条重链的顶端都是轻儿子，因为与轻儿子相连的边是轻边，无法构成重链，所以不会相交。因为每一条重链是连续的，不能通过轻边伸到另一条边去，所以也不会相交。
可是会有两条重链叉在一起吗？
显然是不会的，因为叉在一起必然有若干个公共点，要求每条链编号连续，然而这样无论如何编号不能连续，是不会的。（感性画图理解
嗯，很有道理。
Part 1 预处理
下面，我们就要来开始树剖预处理啦~
树剖的预处理有两次 dfs。
第一次 dfs，我们要维护很少的信息（
| 名称 | 含义 |
|---|---|
| (siz_u) | 以 (u) 为根的子树大小 |
| (fa_u) | (u) 的父亲 |
| (de_u) | (u) 的深度（离根节点的距离） |
| (son_u) | (u) 的重儿子（没有为 (0)） |
这是很轻松就能维护的，代码：
void dfs1(int u,int fat)
//u 是当前点，fat 是 u 的父亲
{
siz[u]=1,fa[u]=fat,de[u]=de[fat]+1;//siz 算上自己，刚开始为 1
int maxn=0;//子树大小最大
for(int p=0;p<tree[u].size();p++)
{
int v=tree[u][p];
if(v==fat)continue;
dfs1(v,u);
siz[u]+=siz[v];//更新 u 的子树大小
if(siz[v]>maxn)//更新 u 的重儿子
son[u]=v,maxn=siz[v];
}
}
然后我们还要维护一些东西：
（注：树剖在线段树的编号是 dfs 序，因为 dfs 序可保证子树序号连续（自己想想就好了））
| 名称 | 用途 |
|---|---|
| (ind_u) | (u) 的 dfs 序，也就是线段树种 (u) 的编号。 |
| (who_c) | dfs 序为 (c) 的节点在树上的编号。 |
| (top_u) | 节点 (u) 的链的顶端。 |
在 dfs 的时候，传参是两个： (u) 和 (T) 表示当前在 (u) 号点，链顶是 (T)。
这里的 dfs 略微复杂一点。首先，如果有重儿子，就沿着重儿子往下跑，这样的话沿着 (T) 下去的链的节点都是连续的（自己想想 dfs 的性质就懂了）。然后我们来遍历剩下的点，如果不是重儿子，说明是轻儿子，此时一条链是断了的，我们以这个轻儿子做新的链顶。
代码：
void dfs2(int u,int T)
{
ind[u]=++cnt,who[cnt]=u,top[u]=T;//ind 和 who 还有 Top 直接维护
if(!son[u])return ;
dfs2(son[u],T);//如上所述
for(int p=0;p<tree[u].size();p++)
{
int v=tree[u][p];
if(v!=fa[u])//不是父亲节点，这是无向图
if(v!=son[u])//不是重儿子，重儿子上面已经判断过了
dfs2(v,v);//我们以这个儿子做新的链的开端
}
}
Part 3 树剖的真正操作
当当当当~你终于看到了真正的树剖操作！
以板子的 4 个操作来讲吧。
第一个操作是路径修改，我们讲了那么多预处理，应该如何维护呢？
- 判断当前 (u) 和 (v) 是否在一个链上，如果不在，转入操作 2，否则转入操作 4。
- 将 (u) 转为链顶深度大的节点（以为它要向链顶跳，每次要体上去）。因为 (top_u) 到 (u) 是一条链上的，编号连续，所以可以用线段树直接修改路径。
- 将 (u) 变为 (top_{fa_u})，跳出这条链，去新链跳。转入操作 1。
- 因为 (u) 和 (v) 在同一条链上，编号连续。我们让 (u) 变成深度小的那个，然后用线段树修改这条链上的路径。
前面铺了那么长，相信这个各位可以很快理解。
void ask_1(int u,int v,int z)
{
z%=Mod;
while(top[u]!=top[v])//1
{
if(de[top[u]]<de[top[v]])swap(u,v);//2
updata(ind[top[u]],ind[u],1,n,1,z);
//3
u=fa[top[u]];
}
//4
if(de[u]>de[v])swap(u,v);
updata(ind[u],ind[v],1,n,1,z);
}
第二个问题是求和，和第一个问题大庭相径，只不过把 2 的修改变成了求和。
int ask_2(int u,int v)
{
int sum=0;
while(top[u]!=top[v])//1
{
if(de[top[u]]<de[top[v]])swap(u,v);
sum+=ask(ind[top[u]],ind[u],1,n,1),sum%=Mod;//2
u=fa[top[u]];//3
}
//4
if(de[u]>de[v])swap(u,v);
sum+=ask(ind[u],ind[v],1,n,1);sum%=Mod;
return sum%Mod;
}
可是第三个和第四个怎么维护？怎么树剖？
这里其实会运用到一个 dfs 序的性质：
以任意点为根的子树，子树 dfs 序必然连续。
这其实也是树剖思想的根基，这个只要你会 dfs，应该很好理解。
那么 (u) 的编号是 (ind_u)，那么它子树 dfs 序最大的一个应该是什么？
因为是连续的，所以应该加上 (siz_u)，但是要减去 (u) 自己，所以是 (ind_u+siz_u-1)，这就是最后一个叶子节点的编号。
void ask_3(int u,int z)
{
updata(ind[u],ind[u]+siz[u]-1,1,n,1,z);
}
int ask_4(int u)
{
return ask(ind[u],ind[u]+siz[u]-1,1,n,1)%Mod;
}
Part 4 关于维护链的工具
维护链的工具有很多种，像线段树啊，树状数组啊，平衡树啊，等等。
平衡树小 SX 不会，也不太清楚怎么维护，所以不评论。（太菜了
不过树状数组建议大家不要使用，因为树状数组维护功能毕竟太少，基本上无法维护太复杂的操作，所以建议用线段树。
反正线段树码量也只占了树剖的 50% 而已
但是，在写线段树的时候，小 SX 要提醒一句，在建树过程中，有的时候 (f_i) 要赋点权初始值，在这个时候，就要写成 (a_{who_l})，因为 (who) 才是这个点在线段树的真正编号。
这里其实也算是提醒我自己，因为这一点我卡了 20min 板子/ch
顺便附上板子的线段树代码；
void build(int l,int r,int now)
{
lazy[now]=0;
int mid=(l+r)>>1;
if(l==r)
{
f[now]=a[who[l]];//这一点上面提到了，供和我一样粗心的菜鸟食用
return ;
}
build(l,mid ,ls(now));
build(mid+1,r,rs(now));
push_up(now);
}
//普通查询和修改，这题和板子没有差别。
int ask(int l,int r,int s,int t,int now)
{
if(l<=s&&r>=t)return f[now];
int mid=(s+t)>>1;
push_down(now,s,t);
int sum=0;
if(l<=mid)sum+=ask(l,r,s,mid ,ls(now)),sum%=Mod;
if(r> mid)sum+=ask(l,r,mid+1,t,rs(now)),sum%=Mod;
return sum;
}
void updata(int l,int r,int s,int t,int now,int val)
{
if(l<=s&&r>=t)
{
push_tag(now,s,t,val);
return ;
}
int mid=(s+t)>>1;
push_down(now,s,t);
if(l<=mid)updata(l,r,s,mid ,ls(now),val);
if(r> mid)updata(l,r,mid+1,t,rs(now),val);
push_up(now);
}
Part 5 有一道叫树的统计的题
话说 08 年 ZJOI 这题是不是用来送分的啊/fad/fad/fad/fad/fad
首先，这里要维护两个值：(S) 和 (M)，(S) 是和，(M) 是最大值。
不难写出线段树代码，一些小细节见注释：
int ls(int now){return now<<1; }
int rs(int now){return now<<1|1;}
void push_up(int now)
{
S[now]=S[ls(now)]+S[rs(now)];
M[now]=max(M[ls(now)],M[rs(now)]);
}
void build(int l,int r,int now)
{
if(l==r)
{
S[now]=M[now]=a[who[l]];//如 Part 4 所述
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls(now));
build(mid+1,r,rs(now));
push_up(now);
}
int ask_max(int l,int r,int s,int t,int now)//区间最大值
{
if(l<=s&&r>=t)return M[now];
int mid=(s+t)>>1,maxn=-0x3f3f3f3f;
if(l<=mid)maxn=max(maxn,ask_max(l,r,s,mid ,ls(now)));
if(r> mid)maxn=max(maxn,ask_max(l,r,mid+1,t,rs(now)));
return maxn;
}
int ask_sum(int l,int r,int s,int t,int now)//区间和
{
if(l<=s&&r>=t)return S[now];
int mid=(s+t)>>1,sum=0;
if(l<=mid)sum+=ask_sum(l,r,s,mid ,ls(now));
if(r> mid)sum+=ask_sum(l,r,mid+1,t,rs(now));
return sum;
}
void updata(int q,int s,int t,int now,int val)
//这里是单点修改，q 是单点修改的位置
{
int mid=(s+t)>>1;
if(s==t)
{
S[now]=M[now]=val;
return ;
}
if(q<=mid)updata(q,s,mid,ls(now),val);//找位置
else updata(q,mid+1,t,rs(now),val);//找位置
push_up(now);
}
至于树剖的预处理基本上是题题相似，所以和最开始摆出来的两个 dfs 一模一样。
然后就是查询的问题了。
QSUM 和 QMAX 其实和我们上面写的查询基本一致，只不过一个求和，一个求最大值，代码：
int QMAX(int u,int v)
{
int maxn=-0x3f3f3f3f;
while(top[u]!=top[v])
{
if(de[top[u]]<de[top[v]])swap(u,v);
maxn=max(maxn,ask_max(ind[top[u]],ind[u],1,n,1));//找链中最大
u=fa[top[u]];
}
if(de[u]>de[v])swap(u,v);
maxn=max(maxn,ask_max(ind[u],ind[v],1,n,1));
return maxn;
}
int QSUM(int u,int v)
{
int sum=0;
while(top[u]!=top[v])
{
if(de[top[u]]<de[top[v]])swap(u,v);
sum+=ask_sum(ind[top[u]],ind[u],1,n,1);//求和
u=fa[top[u]];
}
if(de[u]>de[v])swap(u,v);
sum+=ask_sum(ind[u],ind[v],1,n,1);
return sum;
}
CHANGE 函数也很简单，注意因为是在线段树中查询，所以编号是 (ind_u)。
void CHANGE(int u,int val)
{
updata(ind[u],1,n,1,val);
}
Part 6 当树剖遇上了 LCA
嗯嗯没错，树剖是一种很不错的求 LCA算法。
其实，每次跳链顶的操作，也可以看成找祖宗。当两者跳到了同一条链上，很显然就是深度小的是 LCA，毕竟 LCA 是可以一个节点一个节点往上爬。
树剖常数特别小，像我这样的大常数辣鸡还是 ios+cin/cout 党，也能不卡一点常就能跑到总时间 2.3s 左右，比倍增 2.7s 快了不少。
int get_LCA(int u,int v)
{
while(top[u]!=top[v])
{
if(de[top[u]]<de[top[v]])swap(u,v);
u=fa[top[u]];
}
if(de[u]>de[v])swap(u,v);
return u;
}
就是码量略微大了一丁点，不过个人认为树剖更好写。
好啦，树链剖分的学习笔记就写到这里啦~
完结撒花✿✿ヽ(°▽°)ノ✿