线段树入门
本文原文链接为线段树入门,转载请注明原文连接并附此声明。
蒟蒻刚学完线段树不久,写一篇线段树入门笔记。
线段树是一种二叉搜索树,是 $OI$ 中很重要的数据结构。其支持单点修改,区间修改,单点查询,区间查询(最大最小值、求和)等操作。虽然比树状数组慢,但是它支持的操作更多。
线段树可以高效地解决具有区间性质的问题,例如区间求和,一次操作(修改,查询)就要遍历整个数组,单次操作时间复杂度 $O(n)$ ,$q$ 次修改复杂度 $O(nq)$ ,远远超时。而线段树单次修改时间复杂度 $O(\log n)$ , $q$ 次修改复杂度 $O(q \log n)$ ,节约的不少时间。
线段树基本结构
比如一个长度为 $5$ 的集合 ${8,3,11,4,13}$ ,要维护他它的区间总和,建造出的线段树如下图所示:
如图所示,线段树的性质如下:
$1.$ 线段树的每一个节点都管理着一段区间,其值为这一区间内需要维护的值,根节点(编号为 $1$ )管理着整段区间 $[1,n]$ ,叶子节点管理的区间长度为 $1$ 。
$2.$ 除叶子节点外,其他节点分别有两个子节点,如当前节点的编号为 $p$ ,则左子节点的编号为 $2p$ ,右子节点的编号为 $2p+1$ 。
$3.$ 如节点 $p$ 的管理区间为 $[l,r]$ ,设此区间的中点为 $mid$ ,则左子节点管理区间的范围是 $[l,mid]$ ,右子节点管理区间的范围是 $[mid+1,r]$ 。
线段树建树
这里以维护区间总和为例子。
我们考虑每个节点需要储存的信息有:当前节点管理区间的左右端点,维护的值,以及标记等(后面会讲到),我们可以用一个结构体存储。
代码:
1 | struct Node{ |
线段树空间一定要开原数组的4倍,不然很有可能爆空间。
因为树具有天然的递归性质,所以我们可以用递归建树。如果当前节点是叶子节点,那么将其赋值为当前区间的值,否则递归build
一下左子树,再build
一下右子树,最后回传一下左右子节点的 $sum$ 就可以了。
代码:
1 | //p为当前节点编号,l为当前区间起点,r为当前区间终点 |
回传pushup
的时候,对于区间性质的问题来说,就是将左右两个节点的答案合并就可以了。
示例图:
区间求和公式如下:
区间最大/最小值公式如下:
代码:
1 | //p为当前节点编号 |
建树时间复杂度可以估计为 $O(n)$ ,因为需要遍历所有的节点。
线段树单点修改
比如要将$a_x$ 的数值修改,就是将线段树中区间起点为 $x$ 且长度为 $1$ 的节点修改,然后再回传回根节点,那么整体的思路如下:
$1.$ 从根节点出发,往下寻找目标节点,修改其值。
$2.$ 将总和回传到根节点。
举个例子,还是之前的集合 ${8,3,11,4,13}$ ,现要将第 $2$ 个数 $3$ 加上 $6$ ,操作如下图所示:
我们可以考虑使用递归实现。如果是目标节点,那么修改,然后return
,否则递归向下,目标在左边就遍历左子树,目标在右边就遍历右子树,最后回传总和就可以了。
代码:
1 | //p为当前节点编号,x为要修改的位置,k为要加上的值 |
单点修改的时间复杂度为 $O(\log n)$ ,因为向下递归到叶子节点是遍历树的深度。
线段树区间查询
单点查询没什么可说的吧,和单点修改类似,我们主要看一下区间查询。
区间查询分为三种情况:
- $1.$ 当前节点的区间包含在查询区间之内,直接返回当前节点的 $sum$ 值。
- $2.$ 当前区间与左子树区间有重叠部分,那么递归搜索左子树,加上答案。
- $3.$ 当前区间右子树区间有重叠部分,那么递归搜索右子树,加上答案。
还是之前那个例子,比如查询区间 $[2,4]$ ,如下图所示:
一般来说查询要加long long
,因为所有数的总和有可能爆int
。
代码:
1 | //p为当前节点编号,l为查询区间的左端点,r为查询区间的右端点 |
区间的时间复杂度为 $O(\log n)$ ,因为每次查询都要将线段树一分为二,最后会分成 $\log n$ 个部分。
P3374 【模板】树状数组 1
虽然此题的题目看起来和线段树毫不相干,但是这可以用线段树去做。
这是一个线段树单点修改,区间查询的模板题。
代码:
1 |
|
因为需要操作 $m$ 次,所以整体时间复杂度为 $O(m \log n)$ 。
线段树区间修改
要把线段树的一段区间修改为某个值,最简单、最暴力的方法是遍历每一个节点暴力单点修改。
但是这种方法的时间复杂度是炸的,单次暴力区间修改时间复杂度 $O(n \log n)$ ,$q$ 次修改时间复杂度 $O(q·n \log n)$ ,甚至比直接暴力循环修改的时间复杂度还多一个 $\log$ 。
为什么这样子复杂度这么高呢?我们可以画个图。集合 ${8,3,11,4,13}$ ,区间 $[1,3]$ 统一加 $5$ ,要修改到的节点如下图所示:
总之可以看到,画绿线的节点都是修改区间下的子节点,其实完全没有逐一修改的必要。我们可以先让区间节点修改了,再加上一个“懒”标记,查询时再下传到子节点里面,这样可以大幅提升效率。
“懒”标记指的是当前节点修改过了,但没有让下边的节点修改的一种标记,可以再查询时需要时下传,大大节省时间,所以是懒标记。
最后
好了,就暂时先写到这里吧,因为这个蒟蒻要卷whk干其他事,就先咕咕了。
已知错误:
由于这个蒟蒻的知识短浅疏忽,误将树形视图的方括号写成了圆括号,因为太多改不过来了。
请各位大佬帮忙指出文章的问题,以免误人子弟。