【树形结构】树链剖分

Samira ·

更新时间:2024-11-10

· 757 次阅读

恶心至极

树链剖分

树链就是树上的路径。
将一棵树划分成若干条链，用数据结构（线段树，平衡树等）去维护每条链，复杂度为O(log⁡2n)O(\log_2n)O(log2n)。

重链剖分

剖分有三种方法：盲目剖分、随机剖分、启发式剖分。
综合比较，启发式剖分是剖分时的最佳选择。

定义size(x)size(x)size(x)为以xxx为根的子树的节点个数。
令vvv为uuu的儿子节点中sizesizesize值最大的节点，那么边(u,v)(u,v)(u,v)被称为重边，树中重边之外的边被称为轻边。
我们称某条路径为重路径（也叫重链），当且仅当它全部由重边组成。
对轻边(u,v)(u,v)(u,v)，size(v)⩽12size(u)size(v)\leqslant\frac 12size(u)size(v)⩽21size(u)。
从根到某一点的路径上，不超过O(log⁡2n)O(\log_2n)O(log2n)条轻边，不超过O(log⁡2n)O(\log_2n)O(log2n)条重路径。

重链剖分的过程为2次dfs：

第一步，找重边（图中的红边）。通过一次dfs，可记下所有的重边。第二步，连重边成重链。以根节点为起点，沿重边向下拓展，拉成重链。不在当前重链上的节点，都以该节点为起点向下重新拉一条重链。

记树中编号为iii的结点在用来维护的数据结构中的新编号为id[i]id[i]id[i]，且rnk[id[i]]=irnk[id[i]]=irnk[id[i]]=i。toptoptop记录每个结点所在重链的起点（深度最小的结点），depdepdep记录每个结点的深度。之后会用到。

int id[maxn],rnk[maxn];
struct edge{
  int to,pre;
  edge(int to=0,int pre=0):to(to),pre(pre){};
};
struct tree{
  edge e[maxn];
  int now[maxn],edgtot=0,idtot=0;
  int fa[maxn],son[maxn],dep[maxn],size[maxn],top[maxn];
  void insert(int u,int v){
    e[++edgtot]=edge(v,now[u]),now[u]=edgtot;
  }
  void find(int x,int cfa,int cdep){
    fa[x]=cfa,dep[x]=cdep,size[x]=1,son[x]=0;
    for(int i=now[x];i;i=e[i].pre){
      int cson=e[i].to;
      if(cson!=fa[x]){
        find(cson,x,cdep+1);size[x]+=size[cson];
        if(size[cson]>size[son[x]])son[x]=cson;
      }
    }
  }
  void connect(int x,int anc){
    id[x]=++idtot,rnk[idtot]=x,top[x]=anc;
    if(son[x])connect(son[x],anc);
    for(int i=now[x];i;i=e[i].pre){
      int cson=e[i].to;
      if(cson!=fa[x]&&cson!=son[x])connect(cson,cson);
    }
  }
};

修改查询结点

直接在数据结构上面修改/查询就行了。注意要使用新的结点编号id[x]id[x]id[x]。

修改查询路径

剖分完之后，每条重链就相当于一段ididid编号连续的区间。
整体修改或查询点uuu和点vvv的路径上的权值：

情况1：如果uuu和vvv在同一条重链上，直接用数据结构（代码中以线段树为例）修改/查询id[u]id[u]id[u]至id[v]id[v]id[v]这段区间的值。情况2：如果uuu和vvv不在同一条重链上，一边进行修改/查询，一边将uuu和vvv往同一条重链上靠（当然是让起点深度大的往上跳），然后就变成了情况1。情况A：若fa[top[u]]fa[top[u]]fa[top[u]]与vvv在同一条重链上，修改/查询点uuu与top[u]top[u]top[u]间的各权值，然后uuu跳至fa[top[u]]fa[top[u]]fa[top[u]]，就变成了情况1。情况B：若uuu向上经过若干条重链和轻边后才与vvv在同一条重链上，不断地修改/查询当前uuu和top[u]top[u]top[u]间的各权值，再将uuu跳至fa[top[u]]fa[top[u]]fa[top[u]]，直到uuu与vvv在同一条重链。情况C：若uuu和vvv都是向上经过若干条重链和轻边，到达同一条重链，每次在点uuu和点vvv中，选择dep[top[x]]dep[top[x]]dep[top[x]]较大的点xxx，修改/查询xxx与top[x]top[x]top[x]间的各权值，再跳至fa[top[x]]fa[top[x]]fa[top[x]]，直到点uuu和点vvv在同一条重链。

...
segment_tree segT;
struct tree{
  edge e[maxn];
  int now[maxn],edgtot=0,idtot=0;
  int fa[maxn],son[maxn],dep[maxn],size[maxn],top[maxn];
  ...
  int query(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
      if(dep[top[x]]dep[y])swap(x,y);
    ans+=segT.query(1,id[x],id[y]);
    return ans;
  }
  void modify(int x,int y,int d){
    while(top[x]!=top[y]){
      if(dep[top[x]]dep[y])swap(x,y);
    segT.modify(1,id[x],id[y],d);
  }
};

修改查询子树

根据dfs序，同一棵子树上的结点的ididid编号也是连续的。表示这棵子树的区间就是以根节点iii的编号id[i]id[i]id[i]为起点、长度为size[i]size[i]size[i]的区间。

...
segment_tree segT;
struct tree{
  edge e[maxn];
  int now[maxn],edgtot=0,idtot=0;
  int fa[maxn],son[maxn],dep[maxn],size[maxn],top[maxn];
  ...
  int query_subtree(int x){
    return segT.query(1,id[x],id[x]+size[x]-1);
  }
  void modify_subtree(int x,int d){
    segT.modify(1,id[x],id[x]+size[x]-1,d);
  }
};

求LCA

若两个点处在同一条重链上，深度低的那个就是LCA。
如果不在同一条重链上，那么就跟前面的修改/查询操作一样，让两个点向上跳，直至它们在一条重链上。

...
segment_tree segT;
struct tree{
  edge e[maxn];
  int now[maxn],edgtot=0,idtot=0;
  int fa[maxn],son[maxn],dep[maxn],size[maxn],top[maxn];
  ...
  int Lca(int x,int y){
    while(top[x]!=top[y]){
      if(dep[top[x]]dep[y])swap(x,y);
    return x;
  }
};

作者：翞达羌

树链剖分树形结构

1024 个赞