2020-2021:teams:wangzai_milk:线段树合并

差别

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

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:线段树合并 [2020/06/02 00:03]
wzx27
+++ 2020-2021:teams:wangzai_milk:线段树合并 [2020/07/11 17:48] (当前版本)
zars19
@@ 行 12: / 行 12: @@
 ==== 简介 ====
-有些树型的题目会需要在一个结点维护一棵线段树，例如每次把 $u$到$v$ 的路径上的每个点内加一个元素 $k$，然后求每个节点中出现次数最多的数，这时可以在每个点开一棵权值线段树，树上差分之后在 $\text{dfs}$ 中不断合并父子节点代表的两棵线段树。
+有些树型的题目会需要在一个结点维护一棵线段树，例如每次把 $u$ 到 $v$ 的路径上的每个点内加一个元素 $k$，然后求每个节点中出现次数最多的数，这时可以在每个点开一棵权值线段树，树上差分之后在 $\text{dfs}$ 中不断合并父子节点代表的两棵线段树。
 {{:2020-2021:teams:wangzai_milk:线段树合并2.png?600|}}
@@ 行 57: / 行 57: @@
 </code>
 ==== 复杂度 ====
-空间复杂度比较要注意（因为涉及数组开多大QAQ），每次 $\text{update}$ 最多开 $logn$ 个点，所以一般开 $mlogn$ 的数组，$m$ 表示 $\text{update}$ 次数，$n$ 表示权值线段树的值域上限。
+空间复杂度比较要注意（因为涉及数组开多大QAQ），每次 $\text{update}$ 最多开 $\log n$ 个点，所以一般开 $m\log n$ 的数组，$m$ 表示 $\text{update}$ 次数，$n$ 表示权值线段树的值域上限。
-<del>时间复杂度的话就不会搞了</del>，主要开销在 $\text{merge}$ 操作上，两个树的公共点越多开销越大（这好像没办法算啊），但注意一点是如果在一颗树上合并了 $n-1$ 次那么这个复杂度不会比直接建一棵完整的线段树来得大。
+同空间复杂度，每次 $\text{update}$ 最多开 $\log n$ 个点，所以这里的时间复杂度是 $O(m\log n)$。而 $merge$ 的复杂度正比于叶子节点的个数，又因为 $m$ 次操作最多产生 $m$ 个叶子，所以最坏的情况就是合并了 $m$ 个叶子节点及其路径，每次合并都是 $\log n$ 级别的，所以这部分的复杂度也是 $O(m\log n)$ 的。
 ==== 例题 ====
@@ 行 183: / 行 183: @@
 [[https://www.luogu.com.cn/problem/P3224|P3224 HNOI2012]永无乡]]
-$n$ 个点，两个操作，一是连接两个点，二是求某个点和所有和他相连的点的第$k$小。
+$n$ 个点，两个操作，一是连接两个点，二是求某个点和所有和他相连的点的第 $k$ 小。
 第 $k$ 小也是权值线段树干的事儿，连接的操作用并查集维护。

2020-2021/teams/wangzai_milk/线段树合并.1591027409.txt.gz · 最后更改: 2020/06/02 00:03 由 wzx27