线段树就是一个能高效维护动态区间的一个数据结构；

他能把一个区间分成多个区间，这些区间根据它们的之间的关系形成一个树形结构。

这个过程可以构建出一颗完全二叉树。

其中线段树的操作有：

        1.修改

        2.查询

比如我们现在要维护一个长度为n的区间的和，那么当n=10的时候，该区间所对应的树为：

可以发现每个节点代表一个区间，每个节点存的是该区间的和；

每个节点的儿子的区间加起来一定等于该节点所代表的区间。这些都是很显然的性质；

所以我们建树的时候应该自底而上的建树。也就是说我必须先把所有的儿子先建好，然后开始根据儿子的值构建父亲；

该部分的代码如下

#include<stdio.h>
#define lson l,m,rt<<1	
#define rson m+1,r,rt<<1|1
const int INF = 1005;
int sum[INF << 2];

void PushUp(int rt)		//根据儿子的值构建父亲的值 
{
	 sum[rt] = sum[rt<<1] + sum[rt<<1|1];
	 return; 
}

void Build(int l,int r,int rt)	//自底而上的构建 
{
	if(l == r)
	{
		scanf("%d",&sum[rt]);
		return ;
	}
	else
	{
		int m = (l + r) / 2;
		Build(lson);
		Build(rson);
		PushUp(rt);
	}
	
}

下面我们讲解一下查询操作：

查询是自上而下的查询：

比如我要查询区间2~5的和。

1.从树的最顶层1~6开始查询，发现2~5不完全覆盖1-6区间，于是把把1~6分成1~3和4~6两个区间(因为2~5在1~3和4~6

           都有一部分）

2.发现2~5不完全覆盖1~3区间，于是把1~3分层1~2和3~3两个区间。（因为2~3在1~2和3~3都有一部分）。

          2~5不完全覆盖4~6，于是把 4~6分层4~5一个区间，因为2~5只在4~5里面有一部分；

3.如果查询的区间完全覆盖当前区间就返回，如果不覆盖，就继续分区间来查询；

如图：

可以发现到最后2~2,3~3,4~5这几个区间是被要查询的区间完全覆盖的。我们只需把这几个区间的加起来即可；

代码如下：

int query(int L,int R,int l,int r,int rt) //L~R指要查询的区间，l~r指当前节点所代表的区间 
{
	if(l >= L && r <= R)
	return sum[rt];
	else
	{
		int sumAdd = 0;
		
		int m = (l + r) / 2;
		int res = 0;
		if(L <= m)
		sumAdd += query(L,R,lson);
		if(R > m)
		sumAdd += query(L,R,rson);
		
		return sumAdd;
	}
}

接着是修改，这里只讲解单点修改。（区间修改会在接下来的博客讲解）

单点修改指的是对区间中的单个点修改，区间修改是指对指定区间进行修改；

单点修改实现起来比较简单；

我们自上而下的寻找，找到这个点之后修改，在回溯的过程更新包含这个点的区间的值；

代码如下：

void update(int p,int v,int l,int r,int rt)  //p代表要对那个点修改，v代表该点修改过后的值; 
{
	if(l == r)
	{
		sum[rt] = v;
		return ;
	}
	else
	{
		int m = (l + r) / 2;
		if(p <= m)
		update(p,v,lson);
		else
		update(p,v,rson);
		PushUp(rt);		//在回溯的时候更新包含该点的区间的值； 
	}
}

完整版代码如下：

#include<stdio.h>
#define lson l,m,rt<<1	
#define rson m+1,r,rt<<1|1
const int INF = 1005;
int sum[INF << 2];

void PushUp(int rt)		//根据儿子的值构建父亲的值 
{
	 sum[rt] = sum[rt<<1] + sum[rt<<1|1];
	 return; 
}

void Build(int l,int r,int rt)	//自底而上的构建 
{
	if(l == r)
	{
		scanf("%d",&sum[rt]);
		return ;
	}
	else
	{
		int m = (l + r) / 2;
		Build(lson);
		Build(rson);
		PushUp(rt);
	}
	
}
int query(int L,int R,int l,int r,int rt) //L~R指要查询的区间，l~r指当前节点所代表的区间 
{
	if(l >= L && r <= R)
	return sum[rt];
	else
	{
		int sumAdd = 0;
		
		int m = (l + r) / 2;
		int res = 0;
		if(L <= m)
		sumAdd += query(L,R,lson);
		if(R > m)
		sumAdd += query(L,R,rson);
		
		return sumAdd;
	}
}
void update(int p,int v,int l,int r,int rt)  //p代表要对那个点修改，v代表该点修改过后的值; 
{
	if(l == r)
	{
		sum[rt] = v;
		return ;
	}
	else
	{
		int m = (l + r) / 2;
		if(p <= m)
		update(p,v,lson);
		else
		update(p,v,rson);
		PushUp(rt);		//在回溯的时候更新包含该点的区间的值； 
	}
} 


int main()
{
	int n;
	scanf("%d",&n);  //n代表区间的长度 
	Build(1,n,1);
	int mark,x,y;
	while(~scanf("%d %d %d",&mark,&x,&y))
	{
		if(mark == 0)  //mark为0代表查询x~y区间值加和； 
		{
			int res = query(x,y,1,n,1);
			printf("%d\n",res);
		}
		else if(mark == 1) 	//mark为1代表将第x的点的值修改为y 
		{
			update(x,y,1,n,1);
		}
		
	}
	
	
	return 0;
}

以上是简单线段树的应用；

该线段树实现了单点修改，区间查询的功能；

比较高级的应用有区间修改，扫描线查询；

如果感兴趣的话可以关注我的博客