轻重链剖分与树上路径操作

Prologue

前置技能

一些定义

  • 树上的路径称为树链
  • 非叶节点的儿子中子树大小最大的儿子为重儿子,其它为轻儿子
  • 从非叶节点到重儿子的边称为重边,其它为轻边
  • 由重边构成的链称为重链,其它为轻链
    • 重链中深度最小的节点为链顶
    • 重链的链顶都是其父节点轻儿子
    • 轻叶节点独自构成一条重链
  • 将树分割为重链和轻链即为剖分
  • 树链剖分就是用数据结构去维护重链和轻链
  • 左闭右开区间跟国际接轨

什么时候用树链剖分

  • 遇到毒瘤出题人的时候
  • 对树上两点见的路径进行修改、查询
  • 对以树上一点为根的子树进行修改、查询

剖分

如图,显然图中有 4 条重链,分别为 (2,4)(2,4) (5)(5) (1,3,6,8)(1,3,6,8) (7)(7) 。由于树形结构具有递归性,剖分的操作我们可以用一次 DFS 来实现。过程大致如下:

  1. 对于到达的节点,将以它为根的子树大小初始化为 1
  2. 递归进入儿子前,令其深度等于父节点深度增加 1 ,并记录它的父节点
  3. 回溯时不断从儿子收集以该节点为子树的大小
  4. 取子树大小最大的儿子为重儿子
1
2
3
4
5
6
7
8
void dfs(int u) {
siz[u]=1;
for(int i=hed[u],v;i;i=nxt[i])
if(!dep[v=ver[i]]) {
dep[v]=dep[u]+1;f[v]=u;dfs(v);siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}

再次观察上图,发现此时还是没有能方便维护树链的索引,可以考虑再对树进行一次遍历来给每个节点分配一个编号,由于 DFS 序的性质,每条链上的编号一定是连续的,这有利于后面的维护。虽然此次遍历基于 DFS 框架,但与 DFS 不同的是,它会优先遍历重儿子,我们暂且称它为重量优先搜索 (wfs,weight first search) ,其过程大致如下:

  1. 对于到达的节点,先给它赋予时间戳 dfn 和链顶 t
  2. 以这个时间戳为下标,将该点的点权赋给线段树要维护的区间
  3. 如果该节点有重儿子,则优先遍历重儿子
  4. 遍历所有轻儿子,递归时以该轻儿子为链顶(即新开一条链)
1
2
3
4
5
6
void wfs(int u,int t) {
range[dfn[u]=++fp]=p[u];up[u]=t;
if(son[u]) wfs(son[u],t);
for(int i=hed[u],v;i;i=nxt[i])
if((v=ver[i])!=f[u]&&v!=son[u]) wfs(v,v);
}

此时每个节点的时间戳如上图所示。

维护

观察上图,一条链上的节点已经被放入同一个区间了,我们可以很方便地用线段树等数据结构进行维护。当要对以一点为根的子树进行修改、查询时,由于 DFS 序的性质,子树内所有节点的时间戳都会大于或等于子树的根节点,只要对区间 [dfn[x],dfn[x]+siz[x]) 进行一次操作即可。

1
2
3
4
5
6
void subModify(int r,int d) {
sgt::modify(1,dfn[r],dfn[r]+siz[r],d);
}
int subQuery(int r) {
return sgt::query(1,dfn[r],dfn[r]+siz[r]);
}

对树上两点间的路径进行操作,过程如下:

  • xxyy 不在同一条链上(即链顶不同)
    1. xx 所在链的链顶深度比 yy 的小,交换 x,yx,y ,即让 xx 始终处于下方(类比 LCA )
    2. xx 到它链顶的区间进行操作(链顶的时间戳小,应作为左端点)
    3. xx 等于它链顶的父节点(类比 LCA 中的把 xx 往上跳)
  • xxyy 在同一条链上
    1. xx 深度比 yy 的小,交换 x,yx,y
    2. 直接对区间 [dfn[x],dfn[y]+1) 进行一次操作即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void pathModify(int x,int y,int d) {
while(up[x]!=up[y]) {
if(dep[up[x]]<dep[up[y]]) x^=y^=x^=y;
sgt::modify(1,dfn[up[x]],dfn[x]+1,d);
x=f[up[x]];
}
if(dep[x]>dep[y]) x^=y^=x^=y;
sgt::modify(1,dfn[x],dfn[y]+1,d);
}
int pathQuery(int x,int y) {
int ans=0;
while(up[x]!=up[y]) {
if(dep[up[x]]<dep[up[y]]) x^=y^=x^=y;
ans=(ans+sgt::query(1,dfn[up[x]],dfn[x]+1))%MOD;
x=f[up[x]];
}
if(dep[x]>dep[y]) x^=y^=x^=y;
return (ans+sgt::query(1,dfn[x],dfn[y]+1))%MOD;
}

最近公共祖先

HLD 也可以求 LCA。而且预处理复杂度只要 O(N)O(N)。而且在一些形态比较特殊的树上,查询的复杂度极低,如在一条链上复杂度为 O(1)O(1)

1
2
3
4
5
int lca(int x,int y) {
while(up[x]^up[y])
if(d[up[x]]<d[up[y]]) y=f[up[y]]; else x=f[up[x]];
return d[x]<d[y]? x:y;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

笔记 算法

评论

您需要成为穿墙的邪仙以加载 Disqus。