刚学会,打算整理一下,所以就写了这个帖子
树链剖分要解释清楚有点麻烦,如果你是来学习树链剖分的,还是需要看专业人士来讲
”近几年来,随着选手对数据结构问题的研究不断深入,留给出题人的命题空间也越来越狭小。因此,在国内的竞赛中,大部分数据结构问题除了在不停的包装原题老生常谈外,还有一种趋势是将经典的序列问题放到树结构或者仙人掌结构上,强行增加选手的代码量。我认为这种行为是非常无趣的,它破坏了很多数据结构问题简洁优美的性质,让题目变得索然无味。”
——吉如一
感觉这段话放在树链剖分上挺合适的……
树链剖分 就是把一棵树分成几条链,把树形变为线性,减少处理难度
所以树链剖分大致可以分成3个板块:
1.怎么把树变成线性的
2.将树变成线性后怎么操作
3.怎么操作&得到答案
我就按照这个顺序一个一个整理下去吧
转化
我暂时只会轻重链剖分,所以……
dfs1
int siz[M],deep[M],f[M],hson[M];
//结点数,深度,父结点,重儿子
void dfs1(int x,int fa){
siz[x]=1;
deep[x]=deep[f[x]=fa]+1;
for(int i:t[x])
if(i!=fa){
dfs1(i,x);
siz[x]+=siz[i];
if(siz[i]>siz[hson[x]]) hson[x]=i;
}
}
dfs2
int id[M],w[M],top[M],tim;
//结点对应的线性位置,线性位置对应的结点,所在链最顶端的结点,计数器
void dfs2(int x,int u){
top[x]=u;
id[x]=++tim;
w[tim]=x;
if(!hson[x]) return;
dfs2(hson[x],u);
for(int i:t[x])
if(i!=f[x]&&i!=hson[x])
dfs2(i,i);
}
挺模板的,只要不打错就行了
线性操作
变成线性后,我们就可以做很多东西了
主席树,平衡树,线段树,树状数组……
嗯,突然很烦有没有
没什么好说的,至少这些东西不应该在这里说(逃
只要不打错就行了(不可能的)
操作&统计答案
这一部分需要因地制宜了
大致可以分成单点操作,链式操作,树上操作
单点:没什么好说的,大家都会
树上:这个也很简单,同一棵树里面所有结点的时间戳都是连续的
比如以x为根结点的树上所有结点加上k
void add_tree(int x,LL k){
add(1,1,n,id[x],id[x]+siz[x]-1,k);
}
链式比较复杂,以加法为例子,我们再次细分
1.对x到y上所有点做加法
void add_chain(int x,int y,LL k){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
add(1,1,n,id[top[x]],id[x],k);
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y);
add(1,1,n,id[x],id[y],k);
}
2.对x到y上所有边做加法,我们把边的权值记录在边对应的儿子结点上,这个可以在dfs1中记录好,这时LCA(x,y)是不用参与加法的
void add_chain(int x,int y,LL k){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
add(1,1,n,id[top[x]],id[x],k);
x=f[top[x]];
}
if(x==y) return ;
if(id[x]>id[y]) swap(x,y);
add(1,1,n,id[x]+1,id[y],k);
}
说完了,总结一下,树链剖分是一个很难用的工具,目的旨在增加选手代码的码量(确信)