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

我想，这也许是因为网上关于线段树的东西太多了，线段树又不像树状数组（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，我们来画个图：

对于每个节点，我们保存这个区间的信息，即此题中的区间和。比如红色的那个格子代表的节点，就保存第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多，导致这个结果的是信息的特殊性质——符合区间减法。
未完待续

• inline
• block