2020-2021:teams:wangzai_milk:树链剖分

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:树链剖分 [2020/05/25 19:37]
zars19 [进阶用法]
+++ 2020-2021:teams:wangzai_milk:树链剖分 [2020/06/05 15:22] (当前版本)
infinity37 [怎么剖]
@@ 行 3: / 行 3: @@
 ===== 是什么 =====
-待开发。大概介绍一下轻重链什么的
+一种树的处理办法，在进行过树链剖分过后，书上任意一条链上的节点都可以用$O(logn)$个连续的区间表示
+==== 一些定义 ====
+一个点的$size$为一个点子树中包括该节点本身的节点个数。
+一个点的重儿子为一个点的儿子中，$size$最大的一个。如果有多个，那么就任取一个作为重儿子。
+我们定义重边为一个点和其重儿子之间的边，而轻边为除了重边之外的其他边。
+重边构成的链为重链。
+我们定义一个点的$top$为该点所在的重链深度最小的点。
+==== 怎么剖 ====
+所谓的树链剖分其实也就是将一颗树的所有边分为轻链和重链两个部分。剖分效果如图。
+{{:2020-2021:teams:wangzai_milk:树链剖分-sample1.png?400|}}
+树链剖分要经过两次深搜。
+第一次深搜以某个节点为根开始深搜得到每个点的重儿子，具体流程为统计每个儿子的$size$，保留其中$size$最大的为重儿子，与此同时确定一的点的父亲，$size$以及其深度。
+<code c++>
+void dfs1(int u)
+{
+    siz[u]=1;
+    for(int i=head[u];~i;i=Edges[i].next)
+    {
+        int v=Edges[i].to;
+        if(v==father[u])continue;
+        father[v]=u;dep[v]=dep[u]+1;
+        dfs1(v);siz[u]+=siz[v];
+        if(siz[v]>siz[son[u]])son[u]=v;
+    }
+}
+</code>
+第二次深搜要维护每个点的$top$，首先根节点的$top$是其本身，对于一个点，如果该点有重儿子，那么优先索其重儿子，而其重儿子的$top$也就是该点的top，对于其他儿子，其$top$就是儿子自身。
+<code c++>
+void dfs2(int u,int t)
+{
+    top[u]=t;
+    if(son[u])dfs2(son[u],t);
+    for(int i=head[u];~i;i=Edges[i].next)
+    {
+        int v=Edges[i].to;
+        if(v==father[u]||v==son[u])continue;
+        dfs2(v,v);
+    }
+}
+</code>
+那么此时，我们对一条链$(x,y)$的询问，我们假设$x$的$top$较深，那么我们就让$x$跳转到$x$的父亲，并处理$x$到$x$的$top$之间这一段重链。一直重复这个过程直到$x$和$y$的$top$相同，然后对当前两点间的重链进行处理。
+示例代码如下。
+<code c++>
+void update(int x,int y)
+{
+    while (top[x]!=top[y])
+    {
+        if (dep[top[x]]<dep[top[y]])swap(x,y);
+        query(num[top[x]],num[x]);
+        x = father[top[x]];
+    }
+    if (dep[x]<dep[y])swap(x,y);
+    query(num[y],num[x]);
+}
+</code>
+那么这样剖分并查询为什么时间复杂度是$O(logn)$的呢，首先dfs的时候优先处理每个点的重儿子，那么一条重链在dfs序列中式一段连续的区间。我们在查询的时候，每次跳到$top$的父亲都会走一条轻边，可以发现$fa_{top_x}$的$size$至少是$top_x$的$size$的二倍，那么我们最多跳转了$log(n)$次就会结束查询。
+通常树链剖分算法会和线段树相结合。
 ===== 怎么用 =====

2020-2021/teams/wangzai_milk/树链剖分.1590406629.txt.gz · 最后更改: 2020/05/25 19:37 由 zars19