转载注明出自bestsort.cn,谢谢合作
线段树
线段树是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改&&单点查询&&区间求和&&区间修改. 另外一个拥有类似功能的是树状数组,但是树状数组最常用的是单点修改&&区间求和. 线段树完全涵盖树状数组所有功能
和树状数组的区别和联系
1.两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树. 2.树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决. 说了这么多,其实线段树就是个二叉树而已,只不过叶子节点记录的是区间之间的和而已 先给一份样图 其中,矩形内的是区间之和,区间外的是数组下标(线段树用数组存数据).不难看出,线段树的左孩子=根节点下标_2,右孩子=根节点下标_2+1,而左右孩子则是根节点将区间二分的结果. 先给出线段树的结构体定义然后咱们再仔细讲讲各种(sao)操作
struct node {
int l,r,w,flag;
} a[maxn<<2]; //4倍空间
结构体里有个延迟标记的东西,咱们下面再说这个问题 需要注意的是如果是n个数,那么线段树需要开4n的空间.理论上是2n-1的空间,但是你递归建立的时候当前节点为r,那么左右孩子分别是2_r,2_r+1,此时编译器并不知道递归已结束,因为你的结束条件是在递归之前的,所以编译器会认为下标访问出错,也就是空间开小了,应该再开大2倍。有时候可能你发现开2,3倍的空间也可以AC,那只是因为测试数据并没有那么大。 至于为什么开4倍,我从网上摘抄了一部分(反正我是看不懂
首先线段树是一棵二叉树,最底层有n个叶子节点(n为区间大小) 那么由此可知,此二叉树的高度为,可证
然后通过等比数列求和
求得二叉树的节点个数,具体公式为
,(x为树的层数,为树的高度+1) 化简可得
,整理之后即为$4n$(近似计算忽略掉-1) 证毕
线段树的基础操作主要有5个: 建树、单点查询、单点修改、区间查询、区间修改。
建树
会建二叉树的话这一条也就没什么说的了 主要就是递归建树而已 其中,k为根节点,l,r分别为左右区间 输入n个数将其建立为线段树只需要调用 build(1,1,n)即可 递归过程应该都能看懂(看不懂回去学二叉树去
1 | void build(int k,int l,int r) { |
延迟标记
这里咱们开始用到上面的变量flag了 上面说了,线段树是支持区间修改的,比如说开始那张图,咱把[1,5]都加上3,总不能把[1,5],[1,3],[4,5],[1,2],[3,3],[4,4],[5,5],[1,1],[2,2]
都修改了啊,这样从第二层一直到第四层那我还要这个线段树干嘛,时间早爆炸了. 这时候,精髓部分来了,诶咱就只修改a[2]这个地方,也就是[1,5],下面的暂时用不上,就不管它.然后让flag=3. 如果下一次需要用到这一部分数据的话,将flag下传,这样查询哪一部分咱就算哪一部分的和,其他的就不管 要将[1,5]这部分+3但是不查询他的话,那么[1,5]的左右孩子也就没有更改的必要了 这个flag就是延迟标记,有了它,我们就只需要将修改过的区域标记,等到查询此部分的时候再向下修改就行了 以线段树区间1-10,初值全为0,[1,5]全部+3为例: 可以看出,[1,5]的子区间内的区间和是不对的(修改后不应该为0~) 没关系,我们只需要修改[1,5]和包含[1,5]的区间的内容即可,然后我们让flag = 3,[1,5]的子区间暂时不用管 (黑色数字代表区间和,红色代表flag的值) 如果接下来查询[1,3]或者[1,5]的其他子区间,我们再向下计算区间和,对于查询[1,3]而言,图是这样子的:
结论已经呼之欲出了: 如果查询的区域有延迟标记flag,就将标记下传,并且左右孩子的和+=flag(左右孩子区间内所存的数) 比如说[1,5]的左孩子区间为1-3,则为3\(3-1+1) = 3*3 具体操作如下
1 | void down(int k) { |
区间修改
区间修改和上面的区间查询代码基本相同,自行研究咯~
1 | void changeinterval(int k,int x,int y,int z) { |
单点查询
其实单点查询完全可以使用上面区间查询的函数,反正都是一样的~ 不过毕竟是模板嘛,还是贴一份代码
1 | void askinterval(int k,int x) { |
单点修改
同样,单点修改也可以使用区间修改的代码,只需要让x和y一样就行.
1 | void changeinterval(int k,int x,int z) { |
线段树模板
1 | //最好是全局开long long |
最后
线段树重要的其实不是它本身,而是以后学习其他相关算法的基石,区间查询 / 修改这个特性使得线段树能够和 树链剖分 或者其他数据结构联动,从而达到解题的目的