2020-2021:teams:legal_string:jxm2001:线段树合并_分裂
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:线段树合并_分裂 [2020/07/26 12:43] jxm2001 |
2020-2021:teams:legal_string:jxm2001:线段树合并_分裂 [2021/07/14 15:53] (当前版本) jxm2001 [算法思想] |
||
|---|---|---|---|
| 行 15: | 行 15: | ||
| 关于合并操作，如果遇到叶子节点或空结点就直接 $\text{return}$，否则跑子树。 | 关于合并操作，如果遇到叶子节点或空结点就直接 $\text{return}$，否则跑子树。 | ||
| - | 关于合并操作的时间复杂度，每次合并时间复杂度为两棵线段树的重叠部分的结点数，所以不会超过较小的那棵线段树的结点数。 | + | 关于合并操作的时间复杂度，每次合并时间复杂度为两棵线段树的重叠部分的结点数，而每次合并一个节点等价于删除一个节点。 |
| - | 所以合并操作的总时间复杂度等于空间复杂度，即 $O(m\log n)$。 | + | 每个节点至多被删除一次，所以合并操作的总时间复杂度等于空间复杂度，即 $O(m\log n)$。 |
| ===== 代码模板 ===== | ===== 代码模板 ===== | ||
2020-2021/teams/legal_string/jxm2001/线段树合并_分裂.1595738632.txt.gz · 最后更改: 2020/07/26 12:43 由 jxm2001
