线段树特别篇 - #include <Seter> - using namespace Orz;

线段树特别篇

Seter posted @ 2012年2月07日 17:24 in Practice with tags SegTree , 3268 阅读

刘雨辰大神某天和我说:线段树这么牛叉的东西,怎么很多算法书上都不讲的?

我想,这也许是因为网上关于线段树的东西太多了,线段树又不像树状数组(BIT),是种非常好懂的东西,所以书上才略过的。

两年下来,我对线段树也总算有些认识了。今天先写个简介,然后再慢慢讨论普通线段树,文艺线段树和二逼线段树。

线段树太神了,东西比较多,一下子写不完,我尽量快点更新……

 


 

 

PS:(l..r)定义为区间l,l+1,l+2...r-1,r;[l,r)定义为左闭右开区间l,l+1,l+2...r-2,r-1。

一、线段树简介,从区间和说起:

Q:区间和问题:有10^6个数的序列和10^6个操作,每次询问l..r区间中的数字和。

A:水题,sum[i]=1..i区间数字和,(l..r)=sum[r]-sum[l-1]

Q:加强版区间和问题:有10^6个数的序列和10^6个操作,每次询问l..r区间中的数字和或将第i个数修改为x。

A:线段树维护区间和。

注意到有了修改后,如果还用上面的方法,那么修改第i个数的时候,sum[i..n]都被修改了!为了避免这种囧境,线段树就出现了。

线段树是一棵二叉树,一般要求维护的信息可以进行区间加减,即一个区间的信息可以用两个区间相加减算出来。

二叉树的每个节点保存一个线段[l,r)。表示[l,r)这整个区间的信息。假设序列的第一个数的标号是0,那么根节点是[0,n)。

为了使二叉树更加平衡,节点[l,r)的两个儿子分别是[l,(l+r)/2)和[(l+r)/2,r)。

叶子节点保存的线段一定是[i,i+1),此时无法再分。易知这颗二叉树的高度上界是logn。

比如n=5,我们来画个图:

[0,5)
[0,2) [2,5)
[0,1) [1,2) [2,3) [3,5)
  [3,4) [3,5)

对于每个节点,我们保存这个区间的信息,即此题中的区间和。比如红色的那个格子代表的节点,就保存第3个数和第4个数的和。

易知,除叶子节点对应原序列中的数字以外,某个节点的信息是可以用其两个儿子加出来的(区间加法),即r->v=r->l->v+r->r->v。

Q:线段树保存的信息必须满足区间减法么?

A:不一定,但是满足区间减法的信息可以用BIT维护加速。

Q:线段树保存的信息必须满足区间加法么?

A:好像是的……当然,不一定是加,只要是由两个区间的信息可以合并出整个区间的信息即可,比如维护区间最小值。

由于一层中的线段合并起来恰好是[0,n),所以i在一层中只出现一次,只要递归往下看看i在哪个儿子中就可以了,同时修改所有经过的节点,时间复杂度显然是O(logn)的。

然后再看询问。假如我们要询问节点[l,r)内[i,j)区间的和([l,r)完全包含[i,j)),分情况讨论:

1:l=i,r=j,那么询问的就是整个区间,直接返回节点保存的信息。

2:[i,j)属于[l,(l+r)/2)或者[(l+r)/2,r),则询问的区间完全在这个节点的其中一个儿子中,递归询问儿子的[i,j)区间和。

3:[i,j)横跨了(l+r)/2。将区间拆为[i,(l+r)/2)和[(l+r)/2,j)由于信息满足区间加法,答案就是左儿子[l,(l+r)>>1)中[i,(l+r)>>1)区间的和加上右儿子[(l+r)>>1,r)中[(l+r)>>1,j)区间的和。

虽然操作3要向下递归两次,但是可以发现,一层中最多递归到两个节点,所以询问也是O(logn)的。

 

 


 

 

二、普通线段树,各种模板。

1:我们实现一下简介中的加强版区间和问题的几个重要函数。节点保存的线段区间端点l..r在递归过程中同步计算,所以不存在节点里面了。

#include <stdio.h>
#define N 100
typedef struct _SegTree{
	struct _SegTree*l,*r;
	int v;
}SegTree,*PSegTree;
SegTree pool[N<<3],*spool=pool;//内存池
#define mid (l+r>>1)
PSegTree BuildSegTree(l,r){
	PSegTree node=spool++;
	if(l+1!=r)node->l=BuildSegTree(l,mid),node->r=BuildSegTree(mid,r);
	return node;
}void SegUpdate(node,l,r,i,x)PSegTree node;int l,r,i,x;{
	if(l+1==r)node->v=x;//到达叶子节点,直接修改
	else{
		if(i<mid)SegUpdate(node->l,l,mid,i,x);//i在当前线段左半部分
		else SegUpdate(node->r,mid,r,i,x);//i在当前线段右半部分
		node->v=node->l->v+node->r->v;//用区间加法来求出当前区间保存的信息
	}
}SegQuery(node,l,r,i,j)PSegTree node;int l,r,i,j;{
	if(l==i&&r==j)return node->v;//情况1
	if(j<=mid)return SegQuery(node->l,l,mid,i,j);//情况2
	if(i>=mid)return SegQuery(node->r,mid,r,i,j);//情况2
	return SegQuery(node->l,l,mid,i,mid)+SegQuery(node->r,mid,r,mid,j);//情况3
}main(){
	int i,x,l,r;
	PSegTree segtree=BuildSegTree(0,N);//初始化一个长度为100,数字全为0的线段树
	i=3;x=5;SegUpdate(segtree,0,N,i-1,x);//将第3个数字改为5
	l=3;r=5;printf("%d\n",SegQuery(segtree,0,N,l-1,r));//询问区间(3..5)的
	return 0;
}

再考虑,如果我们要维护一个前缀和,即每次询问的左端点都是0,那么用线段树好像太浪费了?或者信息满足区间减法,可以用[0,r]的信息减去[0,l-1]来算出[l,r]的信息,如何更快地完成询问和修改操作呢?

答案是:树状数组,BIT。这个东西想起来比较复杂,写起来却非常简单,具体可以自行google。

注意,树状数组保存的序列是从1开始标号的。

对于记忆“修改的时候每次加上x&-x直到越界,询问的时候每次减去x&-x直到0”这个东西,可以这么想:修改第i个数将会使得以i..n为结尾的前缀和改变,那么就要从i开始,不断修改直到比n大;询问[0,i]的数字和的时候,这个区间仅与[0,i]这些数的修改相关,所以从i开始,往前面更新直到0。

用树状数组的话,如果修改一个数,则先要求出这个数与此位置上原数的差,然后相当于给一个数加上/减去一个数。为了方便,代码中的函数的作用是直接把一个数加上一个数。

#include <stdio.h>
#define N 100
int a[N+1];//初始长度为100的BIT,初始值为0
inline void BitAdd(i,x){for(;i<=N;i+=i&-i)a[i]+=x;}
inline BitQuery(x){int ans=0;for(;x;x-=x&-x)ans+=a[x];return ans;}
main(){
	BitAdd(3,5);//将第3个数加5
	printf("%d\n",BitQuery(5)-BitQuery(3-1));//查询区间(3..5)的区间和
	return 0;
}

可以看到,树状数组不仅短而且短,速度也比“普通线段树”快N多,导致这个结果的是信息的特殊性质——符合区间减法。
未完待续

By Seter
  • 无匹配
dizzy 说:
2012年4月14日 11:24

seter。。。。你这个未完待续是要待多久啊。。。。。。。。。

Avatar_small
Seter 说:
2012年4月14日 15:41

这个。。。我也不知道啊 T T 没时间啊现在。。。

YangZX 说:
2012年7月09日 23:53

给会用表格画图的跪了。。

Avatar_small
Seter 说:
2012年7月12日 06:28

给直签PKU的跪烂了

makeecat 说:
2013年2月21日 16:03

有没有讲zkw线段树啊?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee