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

差别

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

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:树链剖分 [2020/06/05 14:07]
infinity37 [一些定义]
+++ 2020-2021:teams:wangzai_milk:树链剖分 [2020/06/05 15:22] (当前版本)
infinity37 [怎么剖]
@@ 行 16: / 行 16: @@
 我们定义一个点的$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/树链剖分.1591337273.txt.gz · 最后更改: 2020/06/05 14:07 由 infinity37