目录
1.线段树是什么?有什么用?
2.线段树的思想
3.浅谈懒标记
4.线段树的应用
5.线段树的进阶
线段树是什么?有什么用?
关于线段树,它长这样:
如图,图片中每个节点都是区间,区间可以有权值,可以进行区间操作,如:
区间和
区间最大子段和
区间最大/最小值
区间修改
每次操作可以达到logn的时间。
线段树的思想
看了线段树,有没有感觉熟悉?没错,这就是分块的思想。
线段树的实现
1.建树
1 | void build(int l,int r,int rt) |
2.区间修改
1 | void update(int l,int r,int rt,int i,int j,int k)//将[i,j]内的数加上k |
3.区间求和
1 | int query(int l,int r,int rt,int i,int j)//查询[i,j]区间求和 |
4.完整代码
1 |
|
浅谈懒标记
看了这个代码,思考,怎么优化?
当然用懒标记了。
懒标记的思想:
区间修改时,不到单点,到区间,只修改当前值,接下来把标记传下去,左右儿子加上,下次遍历到时再重复操作,把标记传下去。
核心操作:
1 | void pushdown(LL l,LL r,LL rt){ |
代码
1 |
|
线段树的应用
题目
分析:
经典的线段树题目,套模板就行了,只要注意一下懒标记就行了,简单的区间修改区间求和。
代码(不加注释,前面讲了,代码仅供参考)
1 |
|
题目
分析 :
简单的单点修改+区间查询,懒操作不需要,修改时要特判一下
代码:
1 |
|
例题
题目1
分析:维护两个值,最大数和区间和,如果区间最大数≤1,就不需要修改了,因为sqrt(1)=1。
题目2
分析:维护最小值就行了
题目3
分析:预处理出D,然后区间修改+求和,维护区间和和最大值,如果最大值≤2就不需要修改了,因为D(2)=2,D(1)=1。
题目4
分析:区间求和+区间取模+单点修改,维护区间和和最大值,如果最大值<要取模的值,就不修改了。
线段树的进阶
线段树还可以求区间最大子段和= =,但比较难,可以选择性学习。
分析:
我们要维护四个变量
s:区间内的最大子段和
l:紧靠左端点的最大子段和
r:紧靠右端点的最大子段和
sum:区间和(好像不要维护??)
现在有一个问题,如何维护?
s有三种情况:
1.s是左儿子的s
2.s是右儿子的s
3.s是左儿子的r+右儿子的l。
l有两种情况:
1.l=左儿子的l
2.l=左儿子的s+右儿子的ls
r有两种情况:
1.r=右儿子的r
2.r=右儿子的s+左儿子的rs
看了上面,得出pushup:
1 | void pushup(int rt) |
接下来,右有一个难点,怎么查询
[l,r]的区间最大子段和有以下几种情况
1.独立的存在于左儿子或右儿子中
2.左儿子的r+右儿子的l
然而如果[l,r]在线段树中是一个节点(单独维护过),直接return s就
代码:
1 |
|
写个文章不容易,求给个评论= =