树链剖分学习笔记

数据结构

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

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

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

我们定义一些东西：

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

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

操作

1.dfs1

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

inline void dfs1(int s,int f){
   dep[s]=dep[f]+1;
   fa[s]=f;
   siz[s]=1;
   int ms=-1;
   for(int i=head[s];i;i=e[i].next){
      int v=e[i].to;
      if(v==f) continue;
      dfs1(v,s);
      siz[s]+=siz[v];
      if(siz[v]>ms){
         son[s]=v;
         ms=siz[v];
      }
   }
}

2.dfs2

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

 inline void dfs2(int s,int tp){
    top[s]=tp;
    in[s]=++idx;
    nw[idx]=w[s];
    if(!son[s]) return ;
    dfs2(son[s],tp);
    for(int i=head[s];i;i=e[i].next){
      int v=e[i].to;
      if(v==fa[s]||v==son[s]) continuel
      dfs2(v,v);
    }
 }