线段树
前置知识
创新互联公司2013年成立,先为策勒等服务建站,策勒等地企业,进行企业商务咨询服务。为策勒企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
二叉树
定义
基本操作复杂度: $ O(logn) $
线段树是一棵二叉树,每个节点表示序列上的一段区间,其中根节点表示区间[1,n]。
从根节点开始,只要区间长度不为1,就将区间划分为两半,并分给两个子节点。
若当前节点表示区间[l,r],
当l≠r时,左孩子表示[l,(l+r)/2],右孩子表示[(l+r)/2+1,r];
当l=r时,该节点为叶子节点。
基本性质
性质1
线段树的总节点数为2n-1。
性质2
线段树的层数约为 $ log_{ 2 } n $ ,即每个叶节点到根节点的距离约为 \(log_{2}n\) 。
性质3
任何区间都可以用不超过 \(2log_{2}n\) 个节点组合而成。
编号
线段树的编号方式通常有两种:即2i和2i+1作i的孩子或按构建顺序编号。
存储
线段树的存储也有两种方式:多个数组或struct结构体。
以struct结构体数组为例:
(lc,rc分别为左右孩子的编号,sum为该区间的总和。
数组大小为序列长度两倍。
至于区间的左右端点[l,r],可以存储,也可以递归时计算。
若需要节省空间,则不存储。)
构建
构建过程递归实现,
void build(int u,int l,int r)
(u为当前节点编号,l,r为区间端点)
从根节点开始构建,递归时计算并代入l,r,若l=r,该点为叶子节点,令sum=序列原值,否则,递归构建左右孩子,之后令sum=sum左孩子+sum右孩子。
在主程序中:
t=1;
build(1,1,n);
即可。
应用
单点修改
修改过程递归实现,
void update(int u,int l,int r,int x,int w)
(u当前节点编号,l和r为区间端点,x为要修改的位置,w为变化量)
从根节点开始修改,若当前点为叶子节点,使sum+=w并返回
否则判断x在左孩子还是右孩子,递归进行修改,之后令sum=左孩子sum+右孩子sum。
在主程序中调用:
update(1,1,n,x,y);
区间和查询
查询过程递归实现,
void query(int u,int l,int r,int ll,int rr)
(u为当前节点,l和r是区间端点,ll和rr分别为所查询区间的左右端点)
需要用外层定义变量ans储存答案。
从根节点开始,首先判断查询区间与节点区间是否完全重合,若重合,ans+=sum并返回,否则判断查询区间是否完全在左孩子或者右孩子,若是则递归查询。否则将查询区间拆分,两侧分别递归查询。
在主程序中:
ans=0;
query(1,1,n,x,y);
维护区间最大值/最小值
区间修改
我们在线段树的每个节点上再储存一个信息,称为“标记”,记为tag,表示该节点所包含的每个位置,都要再加上tag。
首先,像区间询问一样将区间对应到尽量少的节点上,
令它们
sum+=(r-l+1)*w;//增加的区间和
tag+=w;//增加标记
然后将sum信息向上pushup。
区间修改后的单点/区间查询
查询与之前类似,
查询过程递归实现,
void query(int u,int l,int r,int ll,int rr,int w)
但由于标记的出现,多了“下传标记”一步。
下传标记时,孩子的标记要叠加。
类似于pushup,标记下传的过程写入一个
void pushdown(int u,int l,int r)
注
一个节点上的tag一定已经计入自身的sum。
在修改和查询时,只要需要进入子节点,就一定要pushdown。
注意
当维护信息较多时,为简化代码,通常将类似于”a[u].sum=a[a[u].lc].sum+a[a[u].rc].sum”的上传信息的步骤写入void pushup(int u)并调用pushup(u);
并非原创,仅是整理,请见谅
分享标题:线段树
URL标题:http://myzitong.com/article/dsoipoh.html