线段树

2019-11-28 16:01:43来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

线段树

引入:

我们经常会遇到需要维护一个序列的问题,例如,给定一个整数序列,每次操作会修改某个位置或某个区间的值,或是询问你序列中的某个区间内所有数的和。或许你可能回去暴力出奇迹或者使用前缀和,但是当数据很大时,时间复杂度明显是受不了的。那么,就需要引入一种时间复杂度相对较小的数据结构 ——线段树

 


目录

  基础

    ├ 关于线段树

    ├ 建树

    ├ 区间查询

    └ 单点修改

   进阶

    ├ 延迟标记

    │   └ 区间修改 单点查询

    区间修改 区间查询

               标记下传

               标记永久化


基础篇

关于线段树

  线段树是一课二叉树树上的每一个结点对应序列的一段区间,如下图:

       

  不难发现,根节点对应的区间时[0,n-1],而每个结点对应一个区间[l,r],且当l=r时,该结点为叶结点,无左右儿子,否则令 mid = (l + r) / 2 ,则左儿子对应的区间为[l,mid],右儿子为[mid+1,r]。同时,也不难发现,最后一行有n个结点,倒数第二行有n/2个结点,倒数第三行有n/4个结点,以此便可以推出一个线段树有n+n/2+n/4+...+1=2*n+1个结点,但是要注意,线段树数组务必要开4倍。设线段树的深度为h,那么h为O(logn)级别,当我们需要维护的序列长度为2的整数次幂时,这个线段数为满二叉树,否则最后一层可能不满

 


建树

  注:接下来的一系列操作都以求区间和为例

  设序列a:5,3,7,9,6,4,1,2,我们将其用线段树构建出来,即

       

  对应的区间和如图

  

  从图中可以看出除叶结点区间和为它本身外,其他节点的区间和均为其左右儿子区间和之和。以此,可以通过递归建树,并在递归后对其区间和进行维护

 1 void build(int k,int l,int r){   //k为结点编号,l为区间左端点,r为区间右端点 
 2     if (l == r){  //如果该点为叶结点 
 3         sum[k] = a[l];  //区间和即为本身 
 4         return;
 5     }
 6     int mid  = l + r >> 1; //取中间值,位运算优化常数 
 7     build(k << 1,l,mid); //构建左子树 
 8     build(k << 1 | 1,mid + 1,r); //构建右子树 
 9     sum[k] = sum[k << 1] + sum[k << 1 | 1]; //维护该区间区间和 
10 }

区间查询

  如果我们要查询区间和[0,6],那么我们需访问3个区间

  cha

   那么在查询过程中,会有以下三种情况  

    ├ 当前区间与需查询区间无交集,返回 0

    ├ 当前区间被需查询区间完全包含,返回该结点对应区间和

    └ 当前区间与需查询区间有交集,但不被完全包含,递归其左右子树进行查询

1 int query(int k,int x,int y,int l,int r){ //k为结点编号,x为当前区间左端点,y为当前区间右端点,
2                                           //l为需查询区间左端点,r为需查询区间右端点 
3     if (x > r || y < l) return 0; //如果无交集,返回0 
4     if (x >= l && y <= r) return sum[k]; //如果完全包含,返回该结点区间和 
5     int res = 0,mid = x + y >> 1;
6     res = query(k << 1,x,mid,l,r); //递归左子树 
7     res += query(k << 1 | 1,mid + 1,y,l,r); //递归右子树 
8     return res;
9 }

 

 单点修改

  假设要将a1加2,那么我们要重新计算4个结点的值

  改前 

                                          ||

                     \/  

    改后

  那么,在修改时可以用递归的形式修改

  在递归中,可能会有以下几种情况

     当前区间不包括需修改区间,直接返回

     找到需修改的叶结点,修改,返回

     有包含,但不是叶结点,递归修改左右子树

 1 void change(int k,int l,int r,int p,int v){
 2     if (l > p || r < p) return; //若该区间不包含需修改点,直接返回 
 3     if (l == r && l == p){ //若当前即为需修改结点 
 4         sum[l] += v; //修改 
 5         return;
 6     }
 7     int mid = l + r >> 1;
 8     change(k << 1,l,mid,p,v);//递归修改左子树 
 9     change(k << 1 | 1,mid + 1,r,p,v);//递归修改右子树 
10     sum[k] = sum[k << 1] + sum[k << 1 | 1];//维护区间和 
11 } 

 


 

进阶篇

延迟标记

  有时我们需要解决的不只是单点修改、区间询问,而是区间修改、区间询问,那么单纯使用以上的方法已经无法解决问题了,因为我们没有办法高效完成区间修改

   以区间内所有数同时加上一个值,以及单点询问为例进行引入

区间修改,单点查询

  考虑在每个结点上维护一个值addsum,表示这个结点所对应的区间内的所有数都加上了addsum


第一次发布时间:2019.11.28  完成度:45%

 


原文链接:https://www.cnblogs.com/Dfkuaid-210/p/11953598.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:平衡树学习笔记

下一篇:个人项目开源之c++基于epoll实现高并发游戏盒子(服务端+客户端