2020-2021:teams:legal_string:线段树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:线段树 [2020/05/22 23:40] lgwza |
2020-2021:teams:legal_string:线段树 [2020/08/04 12:10] (当前版本) lgwza [思想] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | **格式**：不要使用换行符，会引入一个空格。注意公式和两边的汉字之间空一格。 | ||
| + | **内容**：挺好的。 | ||
| ====== 线段树基础 ====== | ====== 线段树基础 ====== | ||
| 行 5: | 行 7: | ||
| ===== 简介 ===== | ===== 简介 ===== | ||
| - | 考虑这样一个问题：假设我们有一个长度为 $n$ 的整数数列，每次给出 | + | 考虑这样一个问题：假设我们有一个长度为 $n$ 的整数数列，每次给出一个区间 $[L,R]$，要求求出第 $L$ 个数到第 $R$ 个数中的最小值（RMQ 问题）。最简单粗暴的方法就是每次将区间 $[L,R]$ 扫一遍，然后求出最小值，假设有 $m$ 个询问，显然这样的复杂度是 $O(nm)$ 的。线段树是这样一种数据结构：每一个点代表一个区间，存储的是这个区间内的信息（对于本题，区间最小值）。这个点的左儿子存储它表示的区间的左半边，右儿子存储它表示的区间的右半边，以此类推，直至叶子节点（保存单个数的值）。 |
| - | 一个区间 $[L,R]$ ，要求求出第 $L$ 个数到第 $R$ 个数中的最小值（RMQ 问题） | + | |
| - | 最简单粗暴的方法就是每次将区间 $[L,R]$ 扫一遍，然后求出最小值， | + | |
| - | 假设有 $m$ 个询问，显然这样的复杂度是 $O(nm)$ 的。 | + | |
| - | 线段树是这样一种数据结构：每一个点代表一个区间，存储的是这个 | + | |
| - | 区间内的信息（对于本题，区间最小值）。这个点的左儿子存储它表示的区 | + | |
| - | 间的左半边，右儿子存储它表示的区间的右半边，以此类推，直至叶子节点（保存单个数的值）。 | + | |
| ===== 思想 ===== | ===== 思想 ===== | ||
| - | 在查询的时候我只要查询 | + | 在查询的时候我只要查询若干个点的最小值就可以了。注意，我们只需要让查询的点不重不漏包含整个区间 $[L,R]$ 即可，而并不是要找到该区间包含的所有节点。我们递归定义查找过程： |
| - | 若干个点的最小值就可以了。注意，我们只需要让查询的点不重不漏包含整 | + | |
| - | 个区间 $[L,R]$ 即可，而并不是要找到该区间包含的所有节点。我们递归定 | + | |
| - | 义查找过程： | + | |
| 1. 若当前节点区间被查询区间所包含，返回这个区间的值 | 1. 若当前节点区间被查询区间所包含，返回这个区间的值 | ||
| 行 28: | 行 21: | ||
| 4. 合并并返回递归查询的值 | 4. 合并并返回递归查询的值 | ||
| - | 操作2、3 保证了我们每次查到的节点都和查询区间有交集。由于我们 | + | 操作2、3 保证了我们每次查到的节点都和查询区间有交集。由于我们查询的区间是连续的，所以至多有一个点P，它的左右儿子与查询区间都 |
| - | 查询的区间是连续的，所以至多有一个点P，它的左右儿子与查询区间都 | + | 有交集且不是完全覆盖。也就是说我们只有至多两个递归是一直递归到叶子的（在 P 处分叉），所以很简单地证明了查询算法的单次复杂度是 $O(\log n)$ |
| - | 有交集且不是完全覆盖。也就是说我们只有至多两个递归是一直递归到叶子 | + | |
| - | 的（在P 处分叉），所以很简单地证明了查询算法的单次复杂度是 $O(\log n)$ | + | |
| - | 假设RMQ 问题中，我们每次可以修改一个数，我们只需要更新线 | + | 假设 RMQ 问题中，我们每次可以修改一个数，我们只需要更新线段树上从根到叶子的一条路径上的所有节点的信息即可，复杂度仍旧是 |
| - | 段树上从根到叶子的一条路径上的所有节点的信息即可，复杂度仍旧是 | + | $O(\log n)$ 。如果更改一下问题，每次可以修改一个连续的区间，又该怎么操作以保证复杂度呢？我们引入懒标记的概念。懒标记是指在某一个节点上打上标记，表示以这个节点为根的子树的信息都是一样的，查询至此无需继续递归。如果要继续对这棵子树的一部分进行其他修改时，我们需要将懒标记下放给它的左右儿子。所以，进行段修改的算法流程和段查询是完全一致的，只需要在每个需要修改的节点上打上懒标记即可。打懒标记有一个原则：在打标记的同时应该将打上标记的那个节点的信息全部更新完全，而不应该是查询时根据标记现算，那样会大幅增加编程和思维难度。 |
| - | O(log n)。如果更改一下问题，每次可以修改一个连续的区间，又该怎么操 | + | |
| - | 作以保证复杂度呢？ | + | |
| - | 我们引入懒标记的概念。懒标记是指在某一个节点上打上标记，表示以 | + | |
| - | 这个节点为根的子树的信息都是一样的，查询至此无需继续递归。如果要继 | + | |
| - | 续对这棵子树的一部分进行其他修改时，我们需要将懒标记下放给它的左 | + | |
| - | 右儿子。所以，进行段修改的算法流程和段查询是完全一致的，只需要在每 | + | |
| - | 个需要修改的节点上打上懒标记即可。 | + | |
| - | 打懒标记有一个原则：在打标记的同时应该将打上标记的那个节点的 | + | |
| - | 信息全部更新完全，而不应该是查询时根据标记现算，那样会大幅增加编 | + | |
| - | 程和思维难度。 | + | |
| - | 注意到如果我们对一个节点的子树上的点进行了修改，那么我们需要 | + | 注意到如果我们对一个节点的子树上的点进行了修改，那么我们需要使用它的左右儿子的信息对这个点的信息进行更新，这就需要我们维护的 |
| - | 使用它的左右儿子的信息对这个点的信息进行更新，这就需要我们维护的 | + | 信息满足可合并性，例如区间的最小值（一个区间的最小值显然是这个区间前半边的最小值和后半段的最小值中的较小者）。类似地，可合并性被定义为一个区间的某种信息可以通过它前半段的这种信息与后半段的这种信息通过简单的计算得到。类似区间众数、区间次大值等就不满足可合并性。 |
| - | 信息满足可合并性，例如区间的最小值（一个区间的最小值显然是这个区间 | + | |
| - | 前半边的最小值和后半段的最小值中的较小者）。类似地，可合并性被定义 | + | |
| - | 为一个区间的某种信息可以通过它前半段的这种信息与后半段的这种信息 | + | |
| - | 通过简单的计算得到。类似区间众数、区间次大值等就不满足可合并性。 | + | |
| ===== 模板 ===== | ===== 模板 ===== | ||
| - | 一、有一个$n$个数的序列$\{a_n\}$，要求实现三种操作： | + | 一、有一个 $n$ 个数的序列 $\{a_n\}$ ，要求实现三种操作： |
| - | 1.将$a_x$改为$y$; | + | 1.将 $a_x$ 改为 $y$ ; |
| - | 2.将$a_x$加上$y$; | + | 2.将 $a_x$ 加上 $y$ ; |
| - | 3.查询$\sum_{i=l}^ra_i$的值 | + | 3.查询 $\sum_{i=l}^ra_i$ 的值 |
| $1\le n,q\le 10^5$ | $1\le n,q\le 10^5$ | ||
| 行 138: | 行 115: | ||
| </hidden> | </hidden> | ||
| - | 二、有一个$n$个数的序列$\{a_n\}$，要求实现两种操作： | + | 二、有一个 $n$ 个数的序列 $\{a_n\}$ ，要求实现两种操作： |
| - | 1.将$a_x(l\le x \le r)$加上$y$; | + | 1.将 $a_x(l\le x \le r)$ 加上 $y$ ; |
| - | 2.查询$\sum_{i=l}^ra_i$的值 | + | 2.查询 $\sum_{i=l}^ra_i$ 的值 |
| $1\le n,q\le 10^5$ | $1\le n,q\le 10^5$ | ||
| 行 233: | 行 210: | ||
| </hidden> | </hidden> | ||
| - | 三、有一个$n$个数的序列$\{a_n\}$，要求实现三种操作： | + | 三、有一个 $n$ 个数的序列 $\{a_n\}$ ，要求实现三种操作： |
| - | 1.将$a_x(l\le x \le r)$改为$y$; | + | 1.将 $a_x(l\le x \le r)$ 改为 $y$ ; |
| - | 2.将$a_x(l\le x \le r)$加上$y$; | + | 2.将 $a_x(l\le x \le r)$ 加上 $y$ ; |
| - | 3.将$a_x(l\le x \le r)$乘上$y$; | + | 3.将 $a_x(l\le x \le r)$ 乘上 $y$ ; |
| - | 4.查询$\sum_{i=l}^ra_i$的值 | + | 4.查询 $\sum_{i=l}^ra_i$ 的值 |
| $1\le n,q\le 10^5$ | $1\le n,q\le 10^5$ | ||
2020-2021/teams/legal_string/线段树.1590162024.txt.gz · 最后更改: 2020/05/22 23:40 由 lgwza
