线段树,一种可以支持区间查询和区间修改的数据结构。
他可以在O(nlogn)的时间内实现查询某个区间的最大值,最小值,……还有很多神奇的内容。
现在,就让我们走进线段树的神奇世界吧!
注:全篇线段树以维护区间和为例。
1.线段树的特点及原理
1)线段树节点x的左右儿子分别为2*x,2*x+1(如图)
2)线段树的每个节点代表一个区间,每个节点的区间由左右儿子组成。
其中最底层节点的区间为它本身(如图)
3)线段树可以对这些区间进行修改,维护。
2.建树
1)线段树在建树时需要花费大量的空间,需要4*n的空间,否则会RE
因此,本篇采用一种省空间的方法
2) 线段树在建树时,从根节点开始往下递归,一旦遇到区间仅为一个数,为叶子节点(即l==r)则输入值,否则就左右儿子向下递归。
3) 简洁的建树代码
QAQ
struct T{ int l,r,mid,v;//l表示区间左端点,r表示区间右端点,v代表权值 }t[400005];void build(int root,int l,int r){ int mid=(l+r)>>1;//求中间值 t[root].l=l,t[root].r=r,t[root].mid=mid;//保存 if(l==r)//如果访问到叶子节点 { t[root].v=read();//输入 return; } build(root<<1,l,mid); build(root<<1|1,mid+1,r);//递归左右儿子 t[root].v=t[root<<1].v+t[root<<1|1].v;//求值 }//注:(l+r)>>1==(l+r)/2,root<<1==root*2,root<<1|1==root*2+1(对此不懂,右转位运算<<,>>,|(https://en.wikipedia.org/wiki/Operator_associativity或https://www.cnblogs.com/Robin20050901/articles/9869953.html))
3.修改
1)差找到待修改点,并直接修改,再往上递归
2)代码
void add(int root,int x,int val){ if(t[root].l==t[root].r)//找到节点 { t[root].v+=val; return ; } if(x<=t[root].mid)add(root<<1,x,val); else add(root<<1|1,x,val);//左右递归 t[root].v=t[root<<1].v+t[root<<1|1].v;//求值 }
4.查询
1)从根节点向下递归,如果找到整段区间,则返回
2)如果区间分成两段,则左右分别计算,返回总和
3)代码
int query(int root,int a,int b){ int l=t[root].l,r=t[root].r,mid=t[root].mid; if(a==l&&b==r)return t[root].v; if(b<=mid)return query(root<<1,a,b); else if(a>mid)return query(root<<1|1,a,b); else return query(root<<1,a,mid)+query(root<<1|1,mid+1,b); }
最后,衷心的希望大家看了这篇博客后,对线段树有更多的了解
continued