首页 > 笔记 > 线段树学习笔记

线段树学习笔记

线段树概述

线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(logn)。

线段树的每个节点表示一个区间,子节点则分别表示父节点的左右半区间,例如父亲的区间是[a,b],那么(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b]。

线段树的基本操作

下面我们从一个经典的例子来了解线段树,问题描述如下:从数组arr[0…n-1]中查找某个数组某个区间内的最小值,其中数组大小固定,但是数组中的元素的值可以随时更新。

对这个问题一个简单的解法是:遍历数组区间找到最小值,时间复杂度是O(n),额外的空间复杂度O(1)。当数据量特别大,而查询操作很频繁的时候,耗时可能会不满足需求。

另一种解法:使用一个二维数组来保存提前计算好的区间[i,j]内的最小值,那么预处理时间为O(n^2),查询耗时O(1), 但是需要额外的O(n^2)空间,当数据量很大时,这个空间消耗是庞大的,而且当改变了数组中的某一个值时,更新二维数组中的最小值也很麻烦。

我们可以用线段树来解决这个问题:预处理耗时O(n),查询、更新操作O(logn),需要额外的空间O(n)。根据这个问题我们构造如下的二叉树

叶子节点是原始组数arr中的元素
非叶子节点代表它的所有子孙叶子节点所在区间的最小值

例如对于数组[2, 5, 1, 4, 9, 3]可以构造如下的二叉树(背景为白色表示叶子节点,非叶子节点的值是其对应数组区间内的最小值,例如根节点表示数组区间arr[0…5]内的最小值是1):


构建线段树

对于线段树我们可以选择和普通二叉树一样的链式结构。由于线段树是完全二叉树,我们也可以用数组来存储,下面的讨论及代码都是数组来存储线段树,节点结构如下(注意到用数组存储时,有效空间为2n-1,实际空间确不止这么多,比如上面的线段树中叶子节点1、3虽然没有左右子树,但是的确占用了数组空间,实际空间是满二叉树的节点数目:2n-1

定义包含n个节点的线段树 SegTreeNode segTree[n],segTree[0]表示根节点。那么对于节点segTree[i],它的左孩子是segTree[2*i+1],右孩子是segTree[2*i+2]。

我们可以从根节点开始,平分区间,递归的创建线段树,线段树的创建函数如下:

查询线段树

已经构建好了线段树,那么怎样在它上面超找某个区间的最小值呢?查询的思想是选出一些区间,使他们相连后恰好涵盖整个查询区间,因此线段树适合解决“相邻的区间的信息可以被合并成两个区间的并区间的信息”的问题。代码如下,具体见代码解释

举例说明(对照上面的二叉树):


1、当我们要查询区间[0,2]的最小值时,从根节点开始,要分别查询左右子树,查询左子树时节点区间[0,2]包含在查询区间[0,2]内,返回当前节点的值1,查询右子树时,节点区间[3,5]和查询区间[0,2]没有交集,返回正无穷INFINITE,查询结果取两子树查询结果的较小值1,因此结果是1.

2、查询区间[0,3]时,从根节点开始,查询左子树的节点区间[0,2]包含在区间[0,3]内,返回当前节点的值1;查询右子树时,继续递归查询右子树的左右子树,查询到非叶节点4时,又要继续递归查询:叶子节点4的节点区间[3,3]包含在查询区间[0,3]内,返回4,叶子节点9的节点区间[4,4]和[0,3]没有交集,返回INFINITE,因此非叶节点4返回的是min(4, INFINITE) = 4,叶子节点3的节点区间[5,5]和[0,3]没有交集,返回INFINITE,因此非叶节点3返回min(4, INFINITE) = 4, 因此根节点返回 min(1,4) = 1。

单节点更新

单节点更新是指只更新线段树的某个叶子节点的值,但是更新叶子节点会对其父节点的值产生影响,因此更新子节点后,要回溯更新其父节点的值。

比如我们要更新叶子节点4(addVal = 6),更新后值变为10,那么其父节点的值从4变为9,非叶结点3的值更新后不变,根节点更新后也不变。


区间更新

区间更新是指更新某个区间内的叶子节点的值,因为涉及到的叶子节点不止一个,而叶子节点会影响其相应的非叶父节点,那么回溯需要更新的非叶子节点也会有很多,如果一次性更新完,操作的时间复杂度肯定不是O(lgn),例如当我们要更新区间[0,3]内的叶子节点时,需要更新出了叶子节点3,9外的所有其他节点。为此引入了线段树中的延迟标记概念,这也是线段树的精华所在。

延迟标记:每个节点新增加一个标记,记录这个节点是否进行了某种修改(这种修改操作会影响其子节点),对于任意区间的修改,我们先按照区间查询的方式将其划分成线段树中的节点,然后修改这些节点的信息,并给这些节点标记上代表这种修改操作的标记。在修改和查询的时候,如果我们到了一个节点p,并且决定考虑其子节点,那么我们就要看节点p是否被标记,如果有,就要按照标记修改其子节点的信息,并且给子节点都标上相同的标记,同时消掉节点p的标记。

因此需要在线段树结构中加入延迟标记域,本文例子中我们加入标记与addMark,表示节点的子孙节点在原来的值的基础上加上addMark的值,同时还需要修改创建函数build 和 查询函数 query,修改的代码用红色字体表示,其中区间更新的函数为update,代码如下:

区间更新举例说明:当我们要对区间[0,2]的叶子节点增加2,利用区间查询的方法从根节点开始找到了非叶子节点[0-2],把它的值设置为1+2 = 3,并且把它的延迟标记设置为2,更新完毕;当我们要查询区间[0,1]内的最小值时,查找到区间[0,2]时,发现它的标记不为0,并且还要向下搜索,因此要把标记向下传递,把节点[0-1]的值设置为2+2 = 4,标记设置为2,节点[2-2]的值设置为1+2 = 3,标记设置为2(其实叶子节点的标志是不起作用的,这里是为了操作的一致性),然后返回查询结果:[0-1]节点的值4;当我们再次更新区间[0,1](增加3)时,查询到节点[0-1],发现它的标记值为2,因此把它的标记值设置为2+3 = 5,节点的值设置为4+3 = 7;


其实当区间更新的区间左右值相等时([i,i]),就相当于单节点更新,单节点更新只是区间更新的特例。

线段树实战

求区间的最大值、区间求和等问题都是采用类似上面的延迟标记域。自己写去。。。


1 COMMENT

  1. BeiYu2016-09-23 下午5:21

    劲啊QAQ

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×