[数据结构与算法]线段树详解

线段树是一种很重要的数据结构，在ACM中用的较多。用于对数据的更新和查询，主要优势体现在对段的处理上。比如：要将数组a从a【i】~a【j】的元素均加上一个数b，那么将做（j-i+1）次。如果有一个段就表示a【i】~a【j】，那么直接将这个段上的和值sum加上b*（j-i+1）即可，仅需操作一次。（这里只关心一个段的和）。再者，若想要知道a【i】~a【j】的和，需查询a【i】，a【i+1】...a【j】，再将其相加，也就是做（j-i+1）次，如果查询段a【i】~a【j】，直接取出该段的sum即可，当（j-i+1）很大时，查询这个段的复杂度也会远远低于前面的做法。那么，怎样来表示这个一段呢？要表示多少个段呢？下面介绍线段树是怎么做的。

节点定义如下：

struct node{
    int l;       //线段的左端点
    int r;       //线段的右端点
    int value;   //这个线段中各元素的和
};

对于每个节点，应该还有两个指针来表示该节点的左右孩子，用一个数组tree【】来模拟一个树，那么，对于节点tree【v】，它的左孩子节点为tree【i*2】,右孩子节点为tree【2*i+1】。那么左右孩子是什么呢？在线段树中，左右孩子分别是父节点的子区间，如父节点代表【l，r】，

令 int mid=(l+r)/2;则左孩子表示的区间为【l,mid】，右孩子表示的区间为【mid+1,r】。叶子节点x表示区间是【x,x】的一个值，即是原数组中的一个元素。

那么对于value值的设置又是怎么样的呢？是从叶子节点递归设置这个value。直接看代码理解

//建树 节点为v,q区间为[l,r]
void build(int v,int l,int r){ 
	tree[v].l=l;
	tree[v].r=r;
	if(l==r){
		//节点初始化
		tree[v].value=a[r];
		return ;
	}
	int mid=(l+r)>>1;
	build(2*v,l,mid);
	build(2*v+1,mid+1,r);
	//根据左右儿子更新节点value值
	tree[v].value=tree[2*v].value+tree[2*v+1].value;
}

1.更新

更新即维护树上的value值。

在对某一段a【i】~a【j】上的所有元素都加上一个值c的时候，在线段树上是怎么样的呢？首先找到这个段(可能是几个分段，比如找到两个分段（i~k）（k+1~j）)，将每个段上的值都加上（c*（r-l+1）），r和l表示这个段上的区间，（r-l+1）表示这个区间的长度。这样是不是就完成了呢？不！比如给2到5这个段上加上了4*c，那么，当下次查询2到3和的时候，这个加上c*2的操作并没有体现（该操作只在2到5及其祖辈上有体现），那么怎么解决这个问题呢？

有一种做法是找到2到5结点更新后，再对其所有子孙结点进行更新，即也会给表示2到3的结点加上c*2，但是这种做法不好。对长度为n的区间i~j进行更新，复杂度是O(nlogn)，而直接在元素组更新只需要n，这样线段树在更新上就显得没有优势了，而这样在比赛中也往往会TLE。

下面介绍一种记录增量的方法，即给每个结点再加一个域int add；记录更新操作的增量c，初始时每个结点的add均为0，当对2~5区间进行更新操作后，给该结点的add加上一个值c。再下次要对2~3结点进行更新和查询时，再将add传下去。具体操作看代码：

void update(int v,int l,int r,int m){ //更新[l,r]加上数m
	if(tree[v].l==l&&tree[v].r==r){ //找到了并更新
		tree[v].value+=m*(l-r+1);
		tree[v].add=m;
		return ;
	}
	//将add传递给儿子
	if(tree[v].add){
		tree[2*v].add+=tree[v].add;
		tree[2*v+1].add+=tree[v].add;
		tree[v].add=0;//传递完了记得清0
	}
	int mid=(tree[v].l+tree[v].r)/2;
	if(r<=mid) update(2*v,l,r,m); //区间被左儿子覆盖
	else{
		if(l>mid){ //区间被右儿子覆盖
			update(v*2+1,l,r,m);
		}else{
			//横跨左右儿子
			update(v*2,l,mid,m);
			update(v*2+1,mid+1,r,m);
		}
	}
}

2.查询

即查询区间【l，r】上的value

//当前查询节点为v,区间为[l,r]
void query(int v,int l,int r){
	if(tree[v].l==l&&tree[v].r==r){
		ans+=tree[v].value;
		return ;
	}
	//看有没有没有传递完的add
	if(tree[v].add){
		tree[v*2].add+=tree[v].add;
		tree[v*2+1].add+=tree[v].add;
		tree[v].add=0;
	}
	int mid=(tree[v].l+tree[v].r)/2;
	if(r<=mid) query(v*2,l,r); //left
	else{
		if(l>mid) query(2*v+1,l,r); //right
		else{
			query(2*v,l,mid);
			query(2*v+1,mid+1,r);
		}
	}
}

线段树的用法非常灵活，离散化也是经常配合线段树使用的，因为线段树所需要的空间为4*MAX，,MAX为原数据的个数