重链剖分 学习笔记
djwj233
2020-10-07 19:51:31
## 重链剖分用来做什么
是 `树链剖分` 一个最常用的分枝
一种维护 **在树上 动态** 修改、查询的DS
~~又是一个不知道归哪类的算法~~
## 树链剖分主过程
简单说就是两遍 $\texttt{DFS}$，把**树**剖成**链**。
加一个 `线段树`，维护链上的信息。
预处理：
- 第一遍DFS，求出 $\texttt{fa}$，$\texttt{dep}$，$\texttt{siz}$，$\texttt{son}$
- 分别代表 `父亲编号`，`深度`，`子树大小`，`重儿子`（所有儿子中子树最大的一个)
- 第二遍DFS，求出 $\texttt{top}$，$\texttt{id}$，$\texttt{endwith}$，$\texttt{newval}$
- 分别代表 `链头`，`新编号`，`该子树内最后一个新编号`，`新编号为 i 的节点的值`
- 树被剖分成了 $\Theta(\log_2 n)$ 条链。建立 **线段树** 或 **分块** 进行区间维护
修改/查询：
- 按照 $\texttt{top}$ 跳轻重链，具体见代码
- 每次对本段链进行区间修改/查询
## 特别注意
虽说好用，但是码量感人，离线问题尽量用**树上差分**减小码量。
技巧：写代码时先把线段树的部分用暴力修改替换，避免两边都有锅导致调不出来。
## 模板
- [P3384 【模板】轻重链剖分](https://www.luogu.com.cn/problem/P3384)
```cpp
#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fo2(v,a,b) for(v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define rg register
#define il inline
const int N=100010,M=200010;
typedef long long ll;
int n,m,rt,P,arr[N];
#define fe(v,a) for(int v=head[a];v;v=Next[v])
int head[N],Next[M],ver[M],Tot;
void Add(int x,int y)
{
ver[++Tot]=y;
Next[Tot]=head[x],head[x]=Tot;
}
int top[N],newval[N],id[N],end_with[N],tot;
int son[N],siz[N],dep[N],fa[N];
struct Segment_Tree
{
struct node
{
int l,r;
ll sum,add;
#define l(x) a[x].l
#define r(x) a[x].r
#define sum(x) a[x].sum
#define add(x) a[x].add
}a[N<<2];
void build(int p,int l,int r)
{
l(p)=l,r(p)=r;
if(l==r)
{
sum(p)=newval[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
sum(p)=sum(p<<1)+sum(p<<1|1);
}
void spread(int p)
{
if(add(p))
{
add(p<<1)=(add(p<<1)+add(p))%P;
sum(p<<1)=(sum(p<<1)+(r(p<<1)-l(p<<1)+1)*add(p))%P;
add(p<<1|1)=(add(p<<1|1)+add(p))%P;
sum(p<<1|1)=(sum(p<<1|1)+(r(p<<1|1)-l(p<<1|1)+1)*add(p))%P;
add(p)=0;
}
}
void change(int p,int l,int r,int c)
{
if(l<=l(p)&&r(p)<=r)
{
sum(p)=(sum(p)+(r(p)-l(p)+1)*c)%P;
add(p)=(add(p)+c)%P;
return ;
}
spread(p);
int mid=(l(p)+r(p))>>1;
if(l<=mid)change(p<<1,l,r,c);
if(r>mid)change(p<<1|1,l,r,c);
sum(p)=(sum(p<<1)+sum(p<<1|1))%P;
}
int query(int p,int l,int r)
{
if(l<=l(p)&&r(p)<=r)
return sum(p);
spread(p);
int mid=(l(p)+r(p))>>1,ans=0;
if(l<=mid)ans+=query(p<<1,l,r);
if(r>mid)ans=(ans+query(p<<1|1,l,r))%P;
return ans;
}
}T;
void dfs1(int x,int f,int Dep)
{
fa[x]=f,dep[x]=Dep;
siz[x]=1;int y=0;
fe(i,x)
{
y=ver[i];
if(y==f)continue;
dfs1(y,x,Dep+1);
siz[x]+=siz[y];
if(siz[son[x]]<siz[y])son[x]=y;
}
}
void dfs2(int x,int tp)
{
id[x]=++tot,newval[tot]=arr[x];
top[x]=tp;int y=0;
// printf("%d\n",x);
if(son[x])dfs2(son[x],tp);
fe(i,x)
{
y=ver[i];
if(y==fa[x]||y==son[x])continue;
dfs2(y,y);
}
end_with[x]=tot;
}
void add_chain(int x,int y,int z)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
T.change(1,id[top[x]],id[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
T.change(1,id[x],id[y],z);
}
int query_chain(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=(ans+T.query(1,id[top[x]],id[x]))%P;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans=(ans+T.query(1,id[x],id[y]))%P;
return ans;
}
inline void add_subtree(int x,int z)
{ T.change(1,id[x],end_with[x],z); }
inline int query_subtree(int x)
{ return T.query(1,id[x],end_with[x]); }
int main()
{
cin>>n>>m>>rt>>P;
fo(i,1,n)scanf("%d",&arr[i]);
fo(i,2,n)
{
int U,V;
scanf("%d%d",&U,&V);
Add(U,V);Add(V,U);
}
int opt,x,y,z;
dfs1(rt,0,1);dfs2(rt,rt);
T.build(1,1,n);
// fo(i,1,n)
// {
// printf("i=%d top=%d end=%d\n",i,top[i],end_with[i]);
// printf(" id=%d son=%d\n",id[i],son[i]);
// }
// fo(i,1,n)
// {
// printf("%d ",newval[i]);
// }
// puts("");
fo(i,1,m)
{
scanf("%d",&opt);
switch(opt)
{
case 1:
scanf("%d%d%d",&x,&y,&z);
add_chain(x,y,z%P);
break;
case 2:
scanf("%d%d",&x,&y);
printf("%d\n",query_chain(x,y));
break;
case 3:
scanf("%d%d",&x,&z);
add_subtree(x,z%P);
// printf("first=%d last=%d\n",id[x],end_with[x]);
break;
case 4:
scanf("%d",&x);
printf("%d\n",query_subtree(x));
break;
}
// puts("--");
// fo(j,1,n)
// printf("%d ",T.query(1,id[j],id[j]));
// puts("");
}
return 0;
}
```
## 题目精选
推荐[这个题单](https://www.luogu.com.cn/training/1125#problems)
- [P2590 [ZJOI2008]树的统计](https://www.luogu.com.cn/problem/P2590)
- [P3178 [HAOI2015]树上操作](https://www.luogu.com.cn/problem/P3178)
- [P2146 [NOI2015]软件包管理器](https://www.luogu.com.cn/problem/P2146)
模板，略略要动点脑子。
- [P2680 运输计划](https://www.luogu.com.cn/problem/P2680)
二分答案+树剖。
- [P4114 Qtree1](https://www.luogu.com.cn/problem/P4114)
- [P1505 [国家集训队]旅游](https://www.luogu.com.cn/problem/P1505)
边权修改，码量更大。
- [P3313 [SDOI2014]旅行](https://www.luogu.com.cn/problem/P3313)
树剖，每个宗教开一个动态开点线段树。码量极大，不敢写QAQ