[关闭]
@Bei-S 2019-01-10T07:21:04.000000Z 字数 694 阅读 525

树链剖分学习笔记

数据结构


不乱于心,不困于情。不畏将来,不念过往。如此,安好。
——丰子恺 《不宠无惊过一生》


要说其实高一时候st神仙已经讲过一遍了,
但是当时是那种懵逼树下懵逼果,一脸懵逼你和我的感觉。。。

树链剖分主要用于处理树上问题,可以在logn的复杂度内完成一次处理。

我们定义一些东西:

dep:深度
top:链顶节点
id:在线段树中的编号
son:重儿子编号(儿子中子树最大的)
fa:父亲节点编号
以及一些segment_tree的数组

树链剖分可以实现树上两点间查询,修改,子树信息查询,修改,同时它在求LCA上面常数比倍增会小很多。

操作

1.dfs1

第一次dfs,处理出siz,son,dep这种基本信息

  1. inline void dfs1(int s,int f){
  2. dep[s]=dep[f]+1;
  3. fa[s]=f;
  4. siz[s]=1;
  5. int ms=-1;
  6. for(int i=head[s];i;i=e[i].next){
  7. int v=e[i].to;
  8. if(v==f) continue;
  9. dfs1(v,s);
  10. siz[s]+=siz[v];
  11. if(siz[v]>ms){
  12. son[s]=v;
  13. ms=siz[v];
  14. }
  15. }
  16. }

2.dfs2

处理出链顶节点信息以及id

  1. inline void dfs2(int s,int tp){
  2. top[s]=tp;
  3. in[s]=++idx;
  4. nw[idx]=w[s];
  5. if(!son[s]) return ;
  6. dfs2(son[s],tp);
  7. for(int i=head[s];i;i=e[i].next){
  8. int v=e[i].to;
  9. if(v==fa[s]||v==son[s]) continuel
  10. dfs2(v,v);
  11. }
  12. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注