这同样也是我上个星期学的内容，这个星期写博客来回顾一下，不然难免会忘记，○( ＾皿＾)っHiahiahia…

线段树是一种弄个高效的对区间更新以及询问的数据结构，包括询问数组一段区间的和，或一段区间的最大最小值，或者区间的最小公因数等等。并能将正常操作的O(n)的复杂度降低到O(logn)，这无疑是一种翻天覆地的变化。

首先我们来看该如何构建一棵线段树，这里我们以维护区间和为例。

const int MAXN = 1000;
int n, t[4*MAXN];

void Build(int* a, int v, int tl, int tr)
{
	if(tl == tr)
		t[v] == a[tl];
	else{
		int mid = tl + (tr - tl)>>1;
		Build(a,v*2,tl,mid);
		Build(a,v*2+1,mid+1,tr);
		t[v] = t[v*2] + t[v*2+1];
	}
}

 我们采用的是递归建树，先建立子树，再利用子树的信息来构建父节点。期中v代表的是当前节点，v的左孩子为v*2，v的右孩子为v*2+1，这里为了方便起见，数组下标从1开始算起。我们建立了左右子树之后，我们就将左右子树的sum值相加，就是当前节点的sum值。

 

接下来就是更新的维护了，为了简单起见，我们先来做一个单点修改，即零a[pos]加上AddVal。void Update(int v, int tl, int tr, int pos, int AddVal)

void Update(int v, int tl, int tr, int pos, int Val)
{
	if(tl >  tr)
		return; 
	if(tl == tr)
		t[v] = Val;
	else{
		int mid = tl + (tr - tl)>>1;
		if(pos <= mid)
			Update(v*2,tl,mid,pos,Val);
		else
			Update(v*2+1,mid+1,tr,pos,Val);
		t[v] = t[v*2] + t[v*2+1];
	}
}

我们采用的方法就是自底而上的逐级修改，首先修改叶子，再逐个节点向上更新，孩子更新之后，我们就更新父节点，用

t[v] = t[v*2] + t[v*2+1];

来实现。

最后我们讲讲如何查询区间和，算了，上代码吧，突然间心情不好了，哎

int Sum(int v, int tl, int tr, int l, int r)
{
	if(l > r)
		return 0;
	if(l == tl && r == tr)
		return t[v];
	int mid = tl + (tr - tl)>>1;
	int sum = 0;
	if(l <= mid)
		sum += Sum(v<<1,tl,mid,l,r);
	if(r >  mid)
		sum += Sum(v<<1|1,mid+1,tr,l,r); 
}

　　lazy标记下次讲，大过年的，一个新年快乐都没有，我继续自闭吧