
- 时间复杂度
- log(n)(建树为O(n))
- 外文名
- Segment Tree
- 领 域
- 数据结构
- 中文名
- 线段树
- 功 能
- 单点、区间的修改、查询
- 学 科
- 数据结构
-
线段树
2021-01-18 01:28:00文章目录一、线段树二、线段树的基本内容三、线段树的基本操作 一、线段树 1、线段树的树形结构: 线段树是一种二叉搜索树,什么叫做二叉搜索树,首先满足二叉树,每个结点度小于等于二,即每个结点最多有两颗子树...
一、线段树
1、线段树的树形结构:
线段树是一种二叉搜索树,什么叫做二叉搜索树,首先满足二叉树,每个结点度小于等于二,即每个结点最多有两颗子树,何为搜索,我们要知道,线段树的每个结点都存储了一个区间,也可以理解成一个线段,而搜索,就是在这些线段上进行搜索操作得到你想要的答案。
2、线段树的应用:
线段树的适用范围很广,可以在线维护修改以及查询区间上的最值,求和。更可以扩充到二维线段树(矩阵树)和三维线段树(空间树)。对于一维线段树来说,每次更新以及查询的时间复杂度为O(logN)。
3、线段树和其他RMQ算法的区别:
常用的解决RMQ问题有ST算法,二者预处理时间都是O(NlogN),而且ST算法的单次查询操作是O(1),看起来比线段树好多了,但二者的区别在于线段树支持在线更新值,而ST算法不支持在线操作。
线段树不但可以用来处理RMQ问题和求和问题,而且其实线段树的功能远远不止如此,要熟练的理解线段这个概念才能更加深层次的理解线段树。二、线段树的基本内容
每个叶子结点的值就是数组的值,每个非叶子结点的度都为二,且左右两个孩子分别存储父亲一半的区间。每个父亲的存储的值也就是两个孩子存储的值的最大值。
代码:
const int maxn = 100005; int a[maxn],t[maxn<<2]; void Pushup(int k){ t[k] = max(t[k<<1],t[k<<1|1]); } void build(int k,int l,int r){ if(l == r) t[k] = a[l]; else{ int m = l + ((r-l)>>1); build(k<<1,l,m); build(k<<1|1,m+1,r); Pushup(k); } }
三、线段树的基本操作
1.点更新:
代码:
//递归方式更新 updata(p,v,1,n,1); void updata(int p,int v,int l,int r,int k){ if(l == r) a[k] += v,t[k] += v; else{ int m = l + ((r-l)>>1); if(p <= m) updata(p,v,l,m,k<<1); else updata(p,v,m+1,r,k<<1|1); Pushup(k); } }
2.区间查询:
//递归方式区间查询 query(L,R,1,n,1); int query(int L,int R,int l,int r,int k){ if(L <= l && r <= R) return t[k]; else{ int res = -INF; int mid = l + ((r-l)>>1); if(L <= m) res = max(res, query(L,R,l,m,k<<1)); if(R > m) res = max(res, query(L,R,m+1,r,k<<1|1)); return res; } }
3.区间更新:
树状数组中的区间更新我们用了差分的思想,而线段树的区间更新相对于树状数组就稍微复杂一点,这里我们引进了一个新东西,Lazy_tag,字面意思就是懒惰标记的意思,实际上它的功能也就是偷懒= =,因为对于一个区间[L,R]来说,我们可能每次都更新区间中的没个值,那样的话更新的复杂度将会是O(NlogN),这太高了,所以引进了Lazy_tag,这个标记一般用于处理线段树的区间更新。
线段树在进行区间更新的时候,为了提高更新的效率,所以每次更新只更新到更新区间完全覆盖线段树结点区间为止,这样就会导致被更新结点的子孙结点的区间得不到需要更新的信息,所以在被更新结点上打上一个标记,称为lazy-tag,等到下次访问这个结点的子结点时再将这个标记传递给子结点,所以也可以叫延迟标记。
也就是说递归更新的过程,更新到结点区间为需要更新的区间的真子集不再往下更新,下次若是遇到需要用这下面的结点的信息,再去更新这些结点,所以这样的话使得区间更新的操作和区间查询类似,复杂度为O(logN)。void Pushdown(int k){ if(lazy[k]){ lazy[k<<1] += lazy[k]; lazy[k<<1|1] += lazy[k]; t[k<<1] += lazy[k]; t[k<<1|1] += lazy[k]; lazy[k] = 0; } } //递归更新区间 updata(L,R,v,1,n,1); void updata(int L,int R,int v,int l,int r,int k){ if(L <= l && r <= R){ lazy[k] += v; t[k] += v; } else{ Pushdown(k); int m = l + ((r-l)>>1); if(L <= m) update(L,R,v,l,m,k<<1); if(m < R) update(L,R,v,m+1,r,k<<1|1); Pushup(k); } }
注意看Pushdown这个函数,也就是当需要查询某个结点的子树时,需要用到这个函数,函数功能就是更新子树的lazy值,可以理解为平时先把事情放着,等到哪天要检查的时候,就临时再去做,而且做也不是一次性做完,检查哪一部分它就只做这一部分。是不是感受到了什么是Lazy_tag,实至名归= =。
值得注意的是,使用了Lazy_tag后,我们再进行区间查询也需要改变。区间查询的代码则变为:
//递归方式区间查询 query(L,R,1,n,1); int query(int L,int R,int l,int r,int k){ if(L <= l && r <= R) return t[k]; else{ Pushdown(k); int res = -INF; int mid = l + ((r-l)>>1); if(L <= m) res = max(res, query(L,R,l,m,k<<1)); if(R > m) res = max(res, query(L,R,m+1,r,k<<1|1)); return res; } }
其实变动也不大,就是多了一个临时更新子树的值的过程。