树链剖分学习

2024-08-23 17:44

文章标签 学习树链剖分

本文主要是介绍树链剖分学习，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.算法适用：维护树上一段或者某个点的子树权值和，同时支持树上路径大小修改，子树修改

2.实现：将树剖分成一条一条链，重链和轻链。其中，轻链连接非重儿子，重链相反。

3.主体部分：

inline void dfs1(int x,int f,int deep){dep[x]=deep;fa[x]=f;siz[x]=1;int maxson=-1;for(int p:v[x]){if(p==f)continue;dfs1(p,x,deep+1);siz[x]+=siz[p];if(siz[p]>maxson)son[x]=p,maxson=siz[p];}

记录每一个点的深度，重儿子，子树数大小。其中重儿子需要与其他儿子点的权值大小作比较，并记录权值。

inline void dfs2(int x,int topf){dfn[x]=++cnt;wt[cnt]=val[x]; top[x]=topf;if(!son[x])return;dfs2(son[x],topf);for(int p:v[x]){if(p==fa[x]||p==son[x])continue;dfs2(p,p);//对于每一个轻儿子都有一条从它自己开始的链 }
}

记录每一个点的遍历序（方便线段树访问，维护整个序列）。同时将权值映射到dfs序上。遍历时优先遍历重儿子，随后遍历轻儿子（链顶变成改点），维护每一条链的链顶。

4.修改查询：

修改树上编号为 $[x,y]$ 的路径（加k），直到跳到相同链顶。

void upd_range(int x,int y,int k){k%=mod;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])  swap(x,y);st.upd(1,1,n,dfn[top[x]],dfn[x],k);x=fa[top[x]];}if(dep[x]>dep[y])  swap(x,y);st.upd(1,1,n,dfn[x],dfn[y],k);
}

修改子树（子树遍历序连续）。即是 $[dfn[x],dfn[x]+siz[x]-1]$

void upd_son(int x,int k){st.upd(1,1,n,dfn[x],dfn[x]+siz[x]-1,k);
}

int ser_son(int x){res=0;st.query_sum(1,1,n,dfn[x],dfn[x]+siz[x]-1);return res;
}
int ser_sum(int x,int y){int ans=0;while(top[x]!=top[y]){if(dep[x]<dep[y])  swap(x,y);ans+=st.query(1,1,n,dfn[top[x]],dfn[x]);x=fa[top[x]];}if(dep[x]>dep[y])  swap(x,y);ans+=st.query(1,1,n,dfn[x],dfn[y]);return ans;
}

计算时取区间 $(dfn[top[x]],dfn[x])$ ，每次计算完成后跳到链顶的父亲。