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

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

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

其中线段树的操作有:

        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;
}

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

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

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

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