本文主要是介绍线段树 001- 概述，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线段树就是一个能高效维护动态区间的一个数据结构；
他能把一个区间分成多个区间，这些区间根据它们的之间的关系形成一个树形结构。
这个过程可以构建出一颗完全二叉树。
其中线段树的操作有：
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);elseupdate(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);elseupdate(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;
}以上是简单线段树的应用；
该线段树实现了单点修改，区间查询的功能；
比较高级的应用有区间修改，扫描线查询；
如果感兴趣的话可以关注我的博客
这篇关于线段树 001- 概述的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
