2020-2021:teams:hotpot:treechain
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:treechain [2020/07/22 13:39] misakatao 更新 |
2020-2021:teams:hotpot:treechain [2020/07/22 13:52] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 244: | 行 244: | ||
| 在上面我们已经提到，按照跳链的策略，能够把两个点都跳到它们LCA所在的重链上，那么当这两个点都跳到同一个重链上时，我们只需要找其中深度更小的那个就能找到两个点的LCA了，时间复杂度$O(\log n)$。 | 在上面我们已经提到，按照跳链的策略，能够把两个点都跳到它们LCA所在的重链上，那么当这两个点都跳到同一个重链上时，我们只需要找其中深度更小的那个就能找到两个点的LCA了，时间复杂度$O(\log n)$。 | ||
| + | ======长链剖分====== | ||
| + | 与树链剖分不同，我们还可以按照子树中深度最大的叶子深度最大的点进行长链剖分，例如下图 | ||
| + | |||
| + | {{:2020-2021:teams:hotpot:25.png?400|}} | ||
| + | |||
| + | 我们仿照重链剖分的方式分析，假设我们现在从$i$走到了$f_i$并且经过了一条轻边，那么显然$f_i$至少还有一个儿子，所以根节点至少还有一个深度不小于$dep_i$的子树，那么通过计算我们会发现从一个点到根最多经过$O(\sqrt{n})$条轻边和长链。所以，一般情况下，长链剖分的复杂度是不如重链剖分的。但是特定情况下，长链剖分会比重链剖分更优，比如这个问题——在线查询某个点的第$k$个祖先。 | ||
| + | |||
| + | 首先，一个点的第$k$个祖先所在的长链的长度一定不小于$k$，因为如果小于，那么显然我们把那个祖先所在的长链改成连到这个点的链，一定比之前的长链剖分要长，说明之前的剖分是错误的。有了这个结论，我们先长链剖分并求出倍增数组，然后暴力求出每条长链的链顶的第$k$个祖先以及它向下的$k$个点，由于长链长度和一定是$n$，所以复杂度为$O(n)$。接下来考虑如何在线求出一个节点$x$的第$k$个祖先。首先假设不大于$k$的最大二进制数为$k_b$，则先通过倍增LCA数组从$x$跳至第$k_b$个祖先$x′$处。由于$k − k_b < \frac{k}{2}$，根据我们之前证明的结论，$x′$所在的长链长度应不小于$k_b$，也就严格大于$k−k_b$。而我们已经预处理出了$x′$所在长链的顶端向上或向下的不少于$k−k_b$个节点，这一定覆盖了$x′$的$k−k_b$倍祖先，所以直接利用这个额外信息向上跳即可。 | ||
2020-2021/teams/hotpot/treechain.1595396363.txt.gz · 最后更改: 2020/07/22 13:39 由 misakatao
