差别

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

--- 2020-2021:teams:legal_string:线段树 [2020/08/04 12:09]
lgwza [简介]
+++ 2020-2021:teams:legal_string:线段树 [2020/08/04 12:10] (当前版本)
lgwza [思想]
@@ 行 11: / 行 11: @@
 ===== 思想 =====
-在查询的时候我只要查询
+在查询的时候我只要查询若干个点的最小值就可以了。注意，我们只需要让查询的点不重不漏包含整个区间 $[L,R]$ 即可，而并不是要找到该区间包含的所有节点。我们递归定义查找过程：
-若干个点的最小值就可以了。注意，我们只需要让查询的点不重不漏包含整
-个区间 $[L,R]$ 即可，而并不是要找到该区间包含的所有节点。我们递归定
-义查找过程：
 . 若当前节点区间被查询区间所包含，返回这个区间的值
@@ 行 24: / 行 21: @@
 . 合并并返回递归查询的值
-操作2、3 保证了我们每次查到的节点都和查询区间有交集。由于我们
+操作2、3 保证了我们每次查到的节点都和查询区间有交集。由于我们查询的区间是连续的，所以至多有一个点P，它的左右儿子与查询区间都
-查询的区间是连续的，所以至多有一个点P，它的左右儿子与查询区间都
+有交集且不是完全覆盖。也就是说我们只有至多两个递归是一直递归到叶子的（在 P 处分叉），所以很简单地证明了查询算法的单次复杂度是 $O(\log n)$
-有交集且不是完全覆盖。也就是说我们只有至多两个递归是一直递归到叶子
-的（在 P 处分叉），所以很简单地证明了查询算法的单次复杂度是 $O(\log n)$
-假设 RMQ 问题中，我们每次可以修改一个数，我们只需要更新线
+假设 RMQ 问题中，我们每次可以修改一个数，我们只需要更新线段树上从根到叶子的一条路径上的所有节点的信息即可，复杂度仍旧是
-段树上从根到叶子的一条路径上的所有节点的信息即可，复杂度仍旧是
+ $O(\log n)$ 。如果更改一下问题，每次可以修改一个连续的区间，又该怎么操作以保证复杂度呢？我们引入懒标记的概念。懒标记是指在某一个节点上打上标记，表示以这个节点为根的子树的信息都是一样的，查询至此无需继续递归。如果要继续对这棵子树的一部分进行其他修改时，我们需要将懒标记下放给它的左右儿子。所以，进行段修改的算法流程和段查询是完全一致的，只需要在每个需要修改的节点上打上懒标记即可。打懒标记有一个原则：在打标记的同时应该将打上标记的那个节点的信息全部更新完全，而不应该是查询时根据标记现算，那样会大幅增加编程和思维难度。
- $O(\log n)$ 。如果更改一下问题，每次可以修改一个连续的区间，又该怎么操
-作以保证复杂度呢？
-我们引入懒标记的概念。懒标记是指在某一个节点上打上标记，表示以
-这个节点为根的子树的信息都是一样的，查询至此无需继续递归。如果要继
-续对这棵子树的一部分进行其他修改时，我们需要将懒标记下放给它的左
-右儿子。所以，进行段修改的算法流程和段查询是完全一致的，只需要在每
-个需要修改的节点上打上懒标记即可。
-打懒标记有一个原则：在打标记的同时应该将打上标记的那个节点的
-信息全部更新完全，而不应该是查询时根据标记现算，那样会大幅增加编
-程和思维难度。
-注意到如果我们对一个节点的子树上的点进行了修改，那么我们需要
+注意到如果我们对一个节点的子树上的点进行了修改，那么我们需要使用它的左右儿子的信息对这个点的信息进行更新，这就需要我们维护的
-使用它的左右儿子的信息对这个点的信息进行更新，这就需要我们维护的
+信息满足可合并性，例如区间的最小值（一个区间的最小值显然是这个区间前半边的最小值和后半段的最小值中的较小者）。类似地，可合并性被定义为一个区间的某种信息可以通过它前半段的这种信息与后半段的这种信息通过简单的计算得到。类似区间众数、区间次大值等就不满足可合并性。
-信息满足可合并性，例如区间的最小值（一个区间的最小值显然是这个区间
-前半边的最小值和后半段的最小值中的较小者）。类似地，可合并性被定义
-为一个区间的某种信息可以通过它前半段的这种信息与后半段的这种信息
-通过简单的计算得到。类似区间众数、区间次大值等就不满足可合并性。
 ===== 模板 =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具