高级数据结构(线段树)

Splaying

873人浏览 · 2020-03-01 11:11:00

Splaying · 2020-03-01 11:11:00 发布

一、基本概念

线段树类似于区间树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化技术或者动态开点技术让空间压缩。线段树是建立在线段的基础上，每个结点都代表了一条线段[a,b],通熟一点就是一个节点代表一个区间，如果左右端点值相等那么就是树中的叶节点。下图就是一棵长度范围为[1,10]的线段树。长度范围为[1,L] 的一棵线段树的深度为log (L) + 1。这个显然，而且存储一棵线段树的空间复杂度为O(L）。
在这里插入图片描述

根据图片假设从根节点[1，10]进行层次遍历，并且设置假设索引区间[1，10]的数组下标k = 1.

首先是第一层区间[1，10]的数组下标k = 1。
第二层区间[1，5]的数组下标k = 2，区间[6，10]的数组下标k = 3。他们两个区间的组合恰巧是一个完整的区间[1，10]。左区间[1，5]的下标恰巧是父区间[1，10]的k的两倍，右区间[6，10]的下标恰k巧是父区间[1，10]的k的两倍+ 1。
第三层区间[1，3]的数组下标k = 4，区间[4，5]的数组下标k = 5。而且它们两个区间的组合恰巧是一个完整的区间[1，5]。下标计算同上，以此类推由此可以得出蓝色下标的推算。
如果把每一个区间都看做一个节点的话那么这张线段树图就变成了一个伪二叉搜索树，我们能够利用它的特性搭配刚才所推算得到的数组下标可以将某些算法的时间复杂度优化到O(nlogn)。

二丶问题提出

假设现在有这样一个问题给定一串随机数字，例如给定10个数: a[1] = 1，a[2] = 6，a[3] = 7，a[4] = 9，a[5] = 2，a[6] = 4，a[7] = 7，a[8] = 8，a[9] = 3，a[10] = 5。然后求a[1] + … + a[8]的值是多少？正常的算法就是直接遍历数组从a[1]加到a[8]就完事了，学过C语言就能写。但是如果有m次操作呢而且 n 和 m 非常大( 0 < n < m < 100000)呢？上面的算法可以得到一个O(m*n)时间复杂度，1秒内对付10^12次方的极限是远远不够的，看似这样一个很简单的问题确实值得深思？

假设我们不去修改这个数组里的数据的情况下可以有一个O(n + m)时间复杂度的算法，利用前缀和(dp思想预处理)打标就可以得到。sum[i] = sum[i-1] + a[i]的方程的解释就是前i个数(包含i)的和等于前i-1个数的和加上第i个数。这个时间复杂度是O(n)的，然后查询的时候区间[l，r]的和ans = sum[r] - sum[l-1]；

	int n = 11,m = 100005;		//10个数从1开始需要开辟11个位置 
	int a[n] = {0,1,6,7,9,2,4,7,8,3,5};
	int sum[n];
	memset(sum,0,sizeof(sum));
	for(int i = 1;i < n;i++){		//O(n)预处理
		sum[i] = sum[i-1] + a[i];
	}
	for(int i = 0;i < m;i++){		//O(m) 
		int l ,r;
		cin >> l >> r;
		cout <<  sum[r] - sum[l-1] << endl;	 	//O(1) 
	}

可以看到方法1的时间复杂度确实很好但是它存在一个非常大的弊端：这个序列必须一直保持静态不能修改。哪怕修改一个数组单元的值都要重新打表那么时间复杂度又回到O(nm)了，因为修改一次数据就要打一次这是不合乎要求的甚至比暴力算法还暴力，因此我们推出今天的主角 线段树 ，我们可以利用线段树将这种 “低级” 问题的时间复杂度由 O(nm) 降低到 O(mlogn)。假设n上限是一个int大小也就是 2^31-1。log一下也就回到了31最坏情况下假设m等于10w，那么时间复杂度远远小于310w的，一秒之内绰绰有余。
利用线段树的思想首先建立一颗树，时间复杂度O(n)算是预处理吧。然后对于m次的查询，每一次查询时间复杂度都是logn，以及修改一个单元的值或者针对某一段区间整体加上同一个值或者减掉同一个值或者更改为同一个值时间复杂度都是logn。这样就可以维持一个平衡让修改和查询的复杂度均匀一下都为logn系列

三、线段树

1. 预处理建树

a. 同样采用上面区间的形式，每一个节点都是一段区间的值。比如叶节点[1，1]是a[1]的值；节点[1，3]的值是a[1] + a[2] + a[3]；节点[1，10]表示a[1] + … + a[10]的总和；依次类推…

b. 然后我们根据上面蓝色标记k可以一步一步索引出每一个节点的值。定义一个求和数组s，s[1] = s[2] + s[3]；s[2] = s[4] + s[5]；最后得出s[k] = s[2* k] + s[2* k+1] 的推算公式。(好好看图)

c. 而且根据上面的图可以得到每次可以将一个大区间分解为两个小区间而且两个小区间没有交集。因此左区间可以写为[l，m]，右区间可以写为[m+1，r]，计算公式m = (l + r) / 2。

d. 建树采用递归的经典写法也可以使用zkw的非递归，建立一颗[1，10]的树，每一个单元恰好对应一个数组a的下标。只有当l == r递归到叶节点的时候赋值，此时l 和 r都刚好按顺序是对应的a数组下标，这样数组里的十个元素恰好可以按照顺序无差错的放上去。

e. 放好每个叶节点的值时还需要进行向上更新，否则这是一个失败的打表。区间[6，7]的值可以由区间[6，6] + [7，7]拼凑出来。这样依次向上，同一个父区间下的左右两个区间拼凑一次就能让父区间都存上一段区间的值。最后根节点也就是[1，10]就存下了a[1] + … + a[10]的值了。

f. 由于每个叶节点都访问了一次，那么建树的时间复杂度就是一个O(n)的。这样就预处理完了所有的初始序列。

const int maxn = 100005;
int s[maxn*4],a[maxn];
void build(int k,int l,int r)
{
	if(l == r){
		s[k] = a[l];		//仔细看图理解，
		return ;
	}
	int m = (l+r)/2;
	build(2*k,l,m);			//递归建树左边
	build(2*k+1,m+1,r);		//递归建树右边
	s[k] = s[2*k] + s[2*k+1];		//父区间 = 左子区间 + 右子区间
}

2. 查询操作

a. 由于我们预处理出来了一些特定区间的和是多少，为了让查询的时间复杂度维持在一个logn级别的复杂度，完美的利用线段树的特性。假设查询区间[5，8]的值，根据上图可以将这个区间分为[5，5]和[6，8]组合出来。[5，5]的值可以通过预处理数组s[11]取得，[6，8]的值可以通过s[6]取得。这样我们就可以直接获得a[6] + a[7] + a[8]的值而不用每一个节点都访问节省了很多时间，完美的利用了预处理的那个数组。现在就是怎么动态逼近取得区间[5，5]和区间[6，8]的索引下标k值为多少，因为最开始我们并不知道它们的索引只是我们画了一个图出来。那么我们继续采用二分递归的想法，对完整的线段树区间[l，r]进行二分，一步一步靠近所要查询的区间。

b. 第一种查询情况，当前区间是被查询区间的一个子区间，那么可以直接根据下标k返回当前区间[l，r]的求和。
在这里插入图片描述

c. 当前区间和被查询区间没有交集，那么当前区间肯定不在我要查询的范围内可以直接返回求和值为0，即满足条件r < ql || qr < l就可以直接返回0了，因为继续递归下去也找不到所要找的区间，就像在沙漠里找海一样。
在这里插入图片描述

//在完整的区间[l,r]中取出查询区间[ql,qr]这一段的值。
int query(int k,int l,int r,int ql,int qr)	
{
	if(r < ql || qr < l){			//递归出口1，没有交集的情况
		return 0;
	}
	if(ql <= l && r <= qr){			//递归出口2，子集情况
		return s[k];		//返回当前区间[l,r]的总求和值也就是a[l] + ... +a[r]
	}
	int m = (l+r)/2;
	int s1 = query(2*k,l,m,ql,qr);		//查询当前区间[l，r]下的左区间[l，r]值
	int	s2 += query(2*k+1,m+1,r,ql,qr); //查询当前区间[l，r]下的右区间[m+1，r]值
	return s1 + s2;
}

3.单点更新

单点更新，前面说前缀和做法的时候发现不能修改，前缀和查询的时间复杂度是O(1)，修改的时间复杂度是O(n)的。现在引入线段树让查询和修改的时间复杂度均衡一下都为O(logn)。由于单点更新只涉及一个值的修改，所以依旧采用二分 + 递归访问。只需要在最大深度次数以内一定能够找到索要修改的区间。假设修改为a[5] = a[5] + ans，也就是线段树中对应区间[5，5]的值，那么从根区间[1，10]进来，肯定在左区间[1，5]中而不在右区间[6，10]中。继续递归左区间[1，5]，得到左区间[1，3]和右区间[4，5]。现在在右区间[4，5]中继续递归得到左区间[4，4]和右区间[5，5]。到达叶节点[5，5]进行修改将当前的s[k] += ans。改为需要修改的值，然后逐级返回重新向上求和完成一次新的预处理。写法和查询的写法非常类似。

void update(int k,int l,int r,int ql,int ans)
{
	if(l == r){		//到达需要修改的节点 
		s[k] += ans;
		return ;
	}
	int m = (l+r)/2;
	if(ql <= m){	//被修改的区间[ql,ql]在当前区间下的左区间[l,m]中 
		update(2*k,l,m,ql,ans);
	}
	else{			//否则就在右区间[m+1,r]中 
		update(2*k+1,m+1,r,ql,ans);
	}
	s[k] = max(s[2*k],s[2*k+1]);
}

4.区间更新
假设现在有这样一个操作，给一段区间[l，r]中的每一个数都在原来的基础上加上同一个值ans，那么应该如何更新才能使得时间复杂度比较好呢？

a. 采用(r-l+1)次的单点更新，那么此时时间复杂度最差可以达到n*logn。这显然不合乎要求。所以这种方法几乎可以不考虑，下面引入区间更新操作和思想。

b. 区间更新比较难，区间更新的思想和单点更新的思想不一样单点更新可以直接更新，区间更新是间接更新或者是传递更新。

c. 比如对更新区间[6，10]统一加上一个值ans，区间更新方法就是[6，10]这个整体区间直接让这个节点加上这个区间长度乘一个值ans，所以直接加上(10-6+1)*ans，通俗点说6-10这个区间有叶节点 6 7 8 9 10一共五个。

d. 然后只给区间[6，10]头上一个标记lazy记录该区间下所有节点需要更新的值，然后终止继续向下访问操作。

e. 因为没有必要一次性更新完所有的叶节点的值，被修改的区间下的所有的叶节点都是加上同一个值，利用这一个特性可以直接对大区间整体更新而去忽略具体的每一个叶节点的更新。

f. 线段树无论干什么操作都需要从头开始向下递归。当下次操作走到有标记的区间的时候顺手将父节点的标记传给左右孩子节点，然后取消父节点的标记。利用传递的思想一步一步传，只有最后传到叶节点的时候才把具体的更新操作更新完毕。

g. 向下更新的操作在query操作中也要加入，因为只有先向下传递了更新操作的信息后才可能不会导致错误，不加入的话有可能导致查询到的答案是修改之前的答案。

void push_down(int k,int l,int r)		//向下传递更新
{
	int m = (l + r)/2;
	if(lazy[k]){			//当前区间由标记
		lazy[2*k] += lazy[k];					//传给左孩子
		lazy[2*k+1] += lazy[k];					//传给右孩子
		s[2*k] += (m-l+1)*lazy[k];		//左孩子区间长度*标记的值
		s[2*k+1] += (r-m)*lazy[k];		//右孩子区间长度*标记的值
		lazy[k] = 0;					//取消父节点的标记
	}
}
void update(int k,int l,int r,int ql,int qr,int ans)
{
	if(r < ql || qr < l){			//没有交集的情况
		return ;
	}
	if(ql <= l && r <= qr){			//子集情况			
		s[k] += (r-l+1)*ans;	//[l,r]区间整体长度*ans
		lazy[k] += ans;			//给父节点上标记
		return ; 				//不用继续更新了，当前区间整体修改完了
	}
	push_down(k,l,r);				//向下传递更新，这句话在查询的时候也要加上
	int m = (l+r)/2;
	update(2*k,l,m,ql,qr,ans);		//更新左边
	update(2*k+1,m+1,r,ql,qr,ans);	//更新右边
	s[k] = s[2*k] + s[2*k+1];		//重新区间求和向上更新
}

四、实际应用

有了这些操作之后遇到一些需要在线计算的区间问题时线段树绝对是最好的方法，查询修改的复杂度都是logn级别，而且可以在线并且保证一个优良的时间复杂度O(nlogn)，就是空间复杂度有点不尽人意，实则是一个用空间换时间的数据结构。但是仅仅为了求和修改这种单点更新的操作可以用写法更简单的树状数组(BIT)时间复杂度也是nlogn级别。不过线段树包含树状数组的所有操作，包括树状数组做不了的一些高级操作，动态最长连续上升子序列，动态最长连续子序列，区间染色，扫描线求区间覆盖面积和周长，以及更加高X格的区间第K大数，树链剖分，主席树都是基于基础的线段树的。线段树对于OI和ACMER来说线段树只是一个高级数据结构，一个维护修改查询快速的手段而不应该认为它是一个算法。

基础线段树题解

线段树区间求和，区间最值问题。这一类问题比较简单直白，对线段树向上更新操作改对应的左右向上合并即可。如例子一样简简单单。

利用线段树求逆序对：这时将线段树当做一颗权值线段树去用，对于序列中的每一个数在插入线段树之前先去当前树中查询有多少的值比当前这个值大(逆序对)，然后再将当前这个值插入到线段树中整体维护一个求和的思想。依次进行下去最后就能获得这串序列的逆序对。时间复杂度从冒泡排序O(n^2)模拟的复杂度降低到O(nlogn)。当存在序列值为负数或者序列值分布比较离散的的时候采用离散化，在进行线段树的插入。

线段树维护动态最长连续子序列：此时线段树维护三个东西，定义ls为区间左起向右最大连续长度，定义rs为区间右起向左最大连续长度，定义ms为区间最大连续长度。

a. 更新的时候比较容易想到的就是父节点的最大左连续从左孩子的最大左连续继承过来，父节点的最大右连续从左孩子的最大右连续继承过来。但是如果左孩子是一个满区间的时候右孩子的左连续应该并入父节点的最大左连续中同理如果右孩子是一个满区间的时候左孩子的右连续应该并入父节点的最大右连续中。

b. 父节点的最大连续有三种情况：左孩子的最大连续，右孩子的最大连续，左孩子的右连续 + 右孩子的左连续，三者取最大值就是父节点的最大连续长度。

c. 查询的时候有两种特殊情况，左孩子的最大右连续的左端点 <= 查询节点或者右孩子的最大左连续的右端点 >= 查询节点，那么当前节点在左孩子的右连续 + 右孩子的左连续长度就是答案。否则就继续递归查询区间直到当前节点满足上面两种情况的一种即可。

线段树维护动态最长连续上升子序列：结合维护最长连续子序列的思想，只要满足相邻两个节点的值满足前面的值小于后面的值(a[m] < a[m+1])就将其左右子区间合并。

线段树维护动态区间众数：结合维护最长连续上升子序列的思想，只需要满足相邻两个节点的值相等(a[m] == a[m+1])就将其左右子区间合并。

线段树区间覆盖问题：这类问题一般需要采用离散化，正常的利用区间更新的思想覆盖即可。最后查询遍历一次所有的叶节点的颜色，对所有的颜色标记去重就是最后能看到的广告数量。

线段树扫描线：面积并问题可以利用线段树离散化x坐标，对于矩形的上下两条线加入上位边和下位边。每次利用线段树维护所能看到的x轴的长度，然后利用当前这条线和上一条线的y轴坐标差值每次计算出一个小矩形的面积，将所有的小矩形面积叠加就是答案。周长交问题同样利用线段树的思想，先枚举x轴的每一条线，这次统计的是前一次操作和当前操作x的长度差。然后枚举y轴的每一条线，一样统计长度差；两个长度差叠加就是矩形的长度。