线段树详解

 

第一部分

1.定义：线段树（Segment Tree）是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树

中的一个叶结点。对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为

[(a+b)/2,b]。因此线段树是满二叉树，最后的子节点数目为N，即整个线段区间的长度。使用线段树可以快速的查找某

一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，因此有时需要离散化让

空间压缩。

2.从一个小问题引出线段树

 

问题：在自然数，且所有的数不大于30000的范围内讨论一个问题：现在已知n条线段，把端点依次输入告诉你，然

后有m个询问，每个询问输入一个点，要求这个点在多少条线段上出现过；

基本解法（一）分析：最基本的解法当然就是读一个点，就把所有线段比一下，看看在不在线段中；每次询问都要

把n条线段查一次，那么m次询问，就要运算m*n次，复杂度就是O(m*n)道题m和n都是30000，那么计算量达到10^9；

而计算机1秒的计算量大约是10^8的数量级，所以这种方法无论怎么优化都是超时。因为n条线段是固定的，所以某种

程度上说每次都把n条线段查一遍有大量的重复和浪费；线段树就是可以解决这类问题的数据结构

线段树解题：

已知线段[2,5] [4,6] [0,7]；求点2,4,7分别出现了多少次？

在[0,7]区间上建立一棵满二叉树：

 

每个节点用结构体：
struct line
{
	int left,right;//左端点、右端点
	int n;//记录这条线段出现了多少次，默认为0
}a[16];

//和堆类似，满二叉树的性质决定a[i]的左儿子是a[2*i]、右儿子是a[2*i+1];然后对于已知的线段依次进行插入操作：从树根开始调用递归函数insert

void insert(int s,int t,int step)//要插入的线段的左端点和右端点、以及当前线段树中的某条线段
{
	if (s==a[step].left && t==a[step].right)
	{
		a[step].n++;//插入的线段匹配则此条线段的记录+1
		return;//插入结束返回
	}
	if (a[step].left==a[step].right) return;//当前线段树的线段没有儿子，插入结束返回
	int mid=(a[step].left+a[step].right)/2;
	if (mid>=t) insert(s,t,step*2);//如果中点在t的右边，则应该插入到左儿子
	else if (mid<t) insert(t,s,step*2+1);
	else//否则，中点一定在s和t之间，把待插线段分成两半分别插到左右儿子里面
	{
		insert(s,mid,step*2);
		insert(mid+1,t,step*2+1);
	}
}

 

 三条已知线段插入过程：

[2,5]

--[2,5]与【0,7】比较，分成两部分：[2,3]插到左儿子【0,3】，[4,5]插到右儿子【4,7】

--[2,3]与【0,3】比较，插到右儿子【2,3】；[4,5]和【4,7】比较，插到左儿子【4,5】

--[2,3]与【2,3】匹配，【2,3】记录+1；[4,5]与【4,5】匹配，【4,5】记录+1

[4,6]

--[4,6]与【0,7】比较，插到右儿子【4,7】

--[4,6]与【4,7】比较，分成两部分，[4,5]插到左儿子【4,5】；[6,6]插到右儿子【6,7】

--[4,5]与【4,5】匹配，【4,5】记录+1；[6,6]与【6,7】比较，插到左儿子【6,6】

--[6,6]与【6,6】匹配，【6,6】记录+1

[0,7]

--[0,7]与【0,7】匹配，【0,7】记录+1

插入过程结束，线段树上的记录如下（红色数字为每条线段的记录n）：

询问操作和插入操作类似，也是递归过程，略

2——依次把【0,7】 【0,3】 【2,3】 【2,2】的记录n加起来，结果为2

4——依次把【0,7】 【4,7】 【4,5】 【4,4】的记录n加起来，结果为3

7——依次把【0,7】 【4,7】 【6,7】 【7,7】的记录n加起来，结果为1

不管是插入操作还是查询操作，每次操作的执行次数仅为树的深度——logN

建树有n次插入操作，n*logN，一次查询要logN，m次就是m*logN；总共复杂度O(n+m)*logN，这道题N不超过

30000，logN约等于14，所以计算量在10^5～10^6之间，比普通方法快了1000倍；

这道题是线段树最基本的操作，只用到了插入和查找；删除操作和插入类似，扩展功能的还有测度、连续段数等等，

在N数据范围很大的时候，依然可以用离散化的方法建树。

第二部分：

 

一 概述

线段树，类似区间树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为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）：