线段树（1）

最新推荐文章于 2024-01-09 10:00:09 发布

ConwayTian

最新推荐文章于 2024-01-09 10:00:09 发布

阅读量1k

点赞数

分类专栏：文摘文章标签：数据结构算法扩展

文摘专栏收录该内容

33 篇文章

订阅专栏

给定一段区间和若干查询关于子区间性质（比如元素总和，最大最小值等等）的请求，要求高效返回结果是很常见的要求。接下来几篇文章我详细说一说应对这些需求所用的数据结构。

从求子区间元素和问题说起。给定序列a[1...n],要求从sum(i,j) = a[i]+a[i+1]+...+a[j]很简单，一个循环就可以了。但如果很多个查询过来，每次都循环一遍就太低效了。我们希望能对结果进行缓存，如果有相同的查询可以直接得到结果，至少能利用之前已经算出的值减少计算量（比如求sum(1,10)，之前已经算出sum(1,5)和sum(6,10)就可以直接把它们加起来返回），这就要求把区间分割分成大小不一的子区间，并形成某种层次关系，每个子区间记录自己的总和，查询时把目标区间分成已知子区间的并;为了查询的高效，分解的层数要尽可能少，达到lg(n)级，这实际就是动态规划的一种应用。不同的分解方式就产生了不同的数据结构，这一节先说线段树。

线段树的分法是把区间[a,b]不断二分，直到长度为1，[1,5]的分解结果如下。

易知，线段树必是一棵完全二叉树（即非叶结点必有两孩子），叶结点个数为区间长度L，总结点为2L-1个，高度O(lgL)，可以把它高效地存在数组里面。再有，给定一个区间[a,b],可以把它分解为不超过2lg(b-a)个子区间的并（用归纳法不难证）,比如[2,5]可分解为[2,2],[3,3],[4,5]。这就意味着，对某个区间的查询和修改可以在O(lgn)的时间完成。

线段树的用途，可以是上面提到的求任意子区间和。但由于线段树划分区间的特性，只要所求的信息能够方便地用两段子区间信息加以组合得出，就可以用线段树，只需要在每个结点处附加一些额外信息。下面举几个例子。

1、区间染色问题 POJ 2528

题目大意是，有长度为L(1<=L<=10000000)的一条木板，操作n(1<=O<=10000)次,每次把它的一部分[a,b]贴上海报，问最后至少有一部分露在外面的海报有多少张。

最简单的方法是FloodFill,开一个长度为L的数组，每次操作都把[a,b]之内的值改为海报的编号，最后统计不同的编号个数。但是L太大，数组开不了那么大，所幸n很小，因此涉及的坐标最多有20000个，可以只开20000的数组，把原本的坐标映射到新坐标上去（所谓“离散化”）。但这样最坏情况复杂度还是O(n^2)比较大。用线段树怎么做呢？

容易想到，给每个结点加上额外的域，记录这个区间被染成什么颜色，-1表示未染色。还是以区间[1,5]为例，假设我们要[1,4]染成1号颜色，很简单，找到[1,3],[4,4]标记为1就行了。如下

这就是懒操作。对[1,4]的染色可以不对1...4个每个值都进行修改，只需要在父区间记录整个区间的信息就可以了。但这样有一个问题，假设要把[2,3]染成2号颜色该如何处理？

[2,3]分成[2,2]和[3,3],当然要把它们标记成2,但[1,3]已经不全是1号颜色了，应该标记成-1，这可以在从树根向下搜索的过程顺便完成。但是区间[1,1]的确还是1号颜色，该把它标记成1，感觉有些繁.解决方法是标记下推。在对[1,3]修改之前把它的标记转移到它的两个子结点中，然后标记为-1。至于两子结点最终是什么颜色，在递归插入的过程是就处然处理好了，过程如下：

把[1,3]标记下推	插入[3,3]	插入[2,2]时，把[1,2]标记下推	插入[2,2]完成

最后如何统计可以的编号？从根开始。如果当前结点标记不是-1，说明整个区间都是一种颜色，虽然它的子结点可能标记了其它色，但都无关紧要，因为都已经被覆盖掉了。如果是-1，再递归地统计两个子结点即可。

分析完成。这种染色常扩展到二维矩形，基本还是离散化+二维线段树，以后再说。

参考代码

2、区间和问题 POJ2750

大意是长度为n（小于100000）的一个环，可以任意更改某个值的大小，要求每次修改后都输出当前环中最大的连续子序列和，要求这个子序列不能是整个环。共修改m次（也小于100000）。

先处理环的问题。把环切开，可以构成0,1,...,n-1的数组。如果子序列完全在[0,n-1]之间就容易了。问题是它可能跨越边界，分成[0,i],[j,n-1]的两段。这种情况下，[i+1,j-1]的和必定是最小连续序列和，这样剩下的才能最大，用序列总和减掉就能得到最大和。可以发现，线段树的结点[a,b]要维护3个主要信息，[a,b]的总和，最小连续和，最大连续和。

接下来是如何从两个子区间的信息获得父区间的信息。总和容易，简单加一下就好。最大连续和呢？取子区间的较大者？显然不行。比如两个子区间{4,3,-1000,5},{5,-1000,3 4}，最大连续和都是7，但合起来最大连续和是10.关键在于拼接的地方可能产生更大的和。因此还需要记录从区间左端和右端开始分别取得的最大连续和lmax,rmax是多少,比较left_child->rmax,right_child->lmax,left_child->max_sum,right_child->max_sum取较大者。最小连续和也是如此。这样区间信息的维护就简单了。

对于修改操作，还是递归。从根结点开始。如果到达叶结点，修改后返回;否则让子结点先修改，再根据修改后的子结点更新自己的信息。

最后，如果根结点的最大连续和是整个环的总和，根据题目要求是不行了，这时减掉最小连续和就行了。

参考代码

3、顺序统计问题 POJ 2828

顺序统计是很广泛的一类问题。由于线段树结点的有序性，在结点中附加子树元素个数可以方便地实现顺序统计。比如O(nlgn)的计算逆序对（其实这种方法用二叉搜索树的变形顺序统计树更好，算法导论上有），另一种类似归并排序的分治法大家都会。这里要说的问题很有意思。

题目是说买火车票经常有人插队。假设现在一个人都没有，给出n（可达200000）个人的入队情况，a b表示编号为b的人插到了当前第a个人后面，求出最后队伍的排列。

n较小的话，用链表是很方便的。瓶颈在于要找到队伍的第i个人不得不从链表开始搜索，很慢。可以想到把链表变成二维形成二叉树的结构，每个结点记录以它为根的子树有多少元素，这样找第i个元素就是O(lgn)。举例如下，结点左边的值表示人的编号，右边表示子树大小。假如有人插队到第5个人后面，可以发现，根结点的左子树有3个人，加上根结点自己有4个人，新来的人必定要插入到右子树中。基本思想就是这样，不是本文重点，不再细说。