首页 > 代码库 > 讲解——线段树
讲解——线段树
讲解——线段树
O、引例
A.给出n个数，n<=100，和m个询问，每次询问区间[l，r]的和，并输出。
一种回答：这也太简单了，O（n）枚举搜索就行了。
另一种回答：还用得着o(n）枚举，前缀和o(1)就搞定。
那好，我再修改一下题目。
B.给出n个数，n<=100，和m个操作，每个操作可能有两种：1、在某个位置加上一个数；2、询问区间[l，r]的和，并输出。
回答：o（n）枚举。
动态修改最起码不能用静态的前缀和做了。
好，我再修改题目：
C.给出n个数，n<=1000000，和m个操作，每个操作可能有两种：1、在某个位置加上一个数；2、询问区间[l，r]的和，并输出。
回答：o（n）枚举绝对超时。
那怎么办？这就需要一种强大的数据结构：线段树。
一、基本概念
1、线段树是一棵二叉搜索树，它储存的是一个区间的信息。
2、每个节点以结构体的方式存储，结构体包含以下几个信息：
区间左端点、右端点；（这两者必有）
这个区间要维护的信息（事实际情况而定，数目不等）。
3、线段树的基本思想：二分。
4、线段树一般结构如图所示：
5、特殊性质：
由上图可得，
1、每个节点的左孩子区间范围为[l，mid]，右孩子为[mid+1,r]
2、对于结点k，左孩子结点为2*k，右孩子为2*k+1，这符合完全二叉树的性质
二、线段树的基础操作
注：以下基础操作均以引例中的求和为例，结构体以此为例：
struct node
{
int l,r,w;//l，r分别表示区间左右端点，w表示区间和
}tree[4*n+1];
线段树的基础操作主要有5个：
建树、单点查询、单点修改、区间查询、区间修改。
1、建树，即建立一棵线段树
① 主体思路：a、对于二分到的每一个结点，给它的左右端点确定范围。
b、如果是叶子节点，存储要维护的信息。
c、状态合并。
②代码
void build(int l,int r,int k) { tree[k].l=l;tree[k].r=r; if(l==r)//叶子节点 { scanf("%d",&tree[k].w); return ; } int m=(l+r)/2; build(l,m,k*2);//左孩子 build(m+1,r,k*2+1);//右孩子 tree[k].w=tree[k*2].w+tree[k*2+1].w;//状态合并，此结点的w=两个孩子的w之和 }
③注意
a.结构体要开4倍空间，具体原因还未搞懂，记住就好了。
b.千万不要漏了return语句，因为到了叶子节点不需要再继续递归了。
2、单点查询，即查询一个点的状态，设待查询点为x
①主体思路：与二分查询法基本一致，如果当前枚举的点左右端点相等，即叶子节点，就是目标节点。如果不是，因为这是二分法,所以设查询位置为x，当前结点区间范围为了l，r，中点为 mid，则如果x<=mid，则递归它的左孩子，否则递归它的右孩子
②代码
void ask(int k) { if(tree[k].l==tree[k].r) //当前结点的左右端点相等，是叶子节点，是最终答案 { ans=tree[k].w; return ; } int m=(tree[k].l+tree[k].r)/2; if(x<=m) ask(k*2);//目标位置比中点靠左，就递归左孩子 else ask(k*2+1);//反之，递归右孩子 }
③正确性分析：
因为如果不是目标位置，由if—else语句对目标位置定位，逐步缩小目标范围，最后一定能只到达目标叶子节点。
3、单点修改，即更改某一个点的状态。用引例中的例子，对第x个数加上y
①主体思路
结合单点查询的原理，找到x的位置；根据建树状态合并的原理，修改每个结点的状态。
②代码
void add(int k) { if(tree[k].l==tree[k].r)//找到目标位置 { tree[k].w+=y; return; } int m=(tree[k].l+tree[k].r)/2; if(x<=m) add(k*2); else add(k*2+1); tree[k].w=tree[k*2].w+tree[k*2+1].w;//所有包含结点k的结点状态更新 }
4、区间查询，即查询一段区间的状态，在引例中为查询区间[x,y]的和
①主体思路
②代码
sum(int k) { if(tree[k].l>=x&&tree[k].r<=y) { ans+=tree[k].w; return; } int m=(tree[k].l+tree[k].r)/2; if(x<=m) sum(k*2); if(y>m) sum(k*2+1); }
③正确性分析
情况1，3不用说，对于情况2，最差情况是搜到叶子节点，此时一定满足情况1
5、区间修改，时间原因，日后再补上
现在再回到引例中的问题
先输入n，再输入n个数，
再输入m，
再输入m个询问，询问格式：p,x,y
p=1，表示第x个数+y
p=2，表示查询并输出区间[x,y]的和
p=3，查询并输出点x的值
代码如下
#include<cstdio> using namespace std; int n,m,p,x,y,ans; struct node { int l,r,w; }tree[200001]; inline void build(int l,int r,int k) { tree[k].l=l;tree[k].r=r; if(l==r)//叶子节点 { scanf("%d",&tree[k].w); return ; } int m=(l+r)/2; build(l,m,k*2);//左孩子 build(m+1,r,k*2+1);//右孩子 tree[k].w=tree[k*2].w+tree[k*2+1].w;//此结点的w=两个孩子的w之和 } inline void add(int k) { if(tree[k].l==tree[k].r)//找到目标位置 { tree[k].w+=y; return; } int m=(tree[k].l+tree[k].r)/2; if(x<=m) add(k*2); else add(k*2+1); tree[k].w=tree[k*2].w+tree[k*2+1].w;//所有包含结点k的结点状态更新 } inline void ask(int k) { if(tree[k].l==tree[k].r) //当前结点的左右端点相等，是叶子节点，是最终答案 { ans=tree[k].w; return ; } int m=(tree[k].l+tree[k].r)/2; if(x<=m) ask(k*2);//目标位置比中点靠左，就递归左孩子 else ask(k*2+1);//反之，递归右孩子 } inline void sum(int k) { if(tree[k].l>=x&&tree[k].r<=y) { ans+=tree[k].w; return; } int m=(tree[k].l+tree[k].r)/2; if(x<=m) sum(k*2); if(y>m) sum(k*2+1); } int main() { scanf("%d",&n); build(1,n,1); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&p,&x,&y); ans=0; if(p==1) add(1); else if(p==2) { sum(1); printf("%d\n",ans); } else { ask(1); printf("%d\n",ans); } } }
三、参考题目
1、codevs1080线段树练习 http://codevs.cn/problem/1080/
未完待续
讲解——线段树