【完全版】线段树(转载)

作者: qwq 分类: 算法 发布时间: 2017-07-16 11:31

 

转载至此仅作存档,建议访问原文链接查看。
______

很早前写的那篇线段树专辑至今一直是本博客阅读点击量最大的一片文章,当时觉得挺自豪的,还去PKU打广告,但是现在我自己都不太好意思去看那篇文章了,觉得当时的代码风格实在是太丑了,很多线段树的初学者可能就是看着这篇文章来练习的,如果不小心被我培养出了这么糟糕的风格,实在是过意不去,正好过几天又要给集训队讲解线段树,所以决定把这些题目重新写一遍,顺便把近年我接触到的一些新题更新上去〜;并且学习了喷射等更高级的数据结构后对线段树的体会有更深了一层,线段树的写法也就比以前飘逸,简洁且方便多了。

在代码前先介绍一些我的线段树风格:

  • MAXN是题目给的最大区间,而节点数要开4倍,确切的来说节点数要开大于MAXN的最小2×的两倍
  • LSON和rson分辨表示结点的左儿子和右儿子,由于每次传参数的时候都固定是这几个变数,所以用可以预定于比较网求方便的表示
    以前的写法的英文另外开两个个数组记录每个结点所表示的区间,其实这个区间不必保存,一边算一边传下去就行,只需要写函数的时候多两个参数,结合LSON和rson的预定义可以很方便
  • PushUP(int rt)是把当前结点的信息更新到父结点
  • PushDown(int rt)是把当前结点的信息更新给儿子结点
  • 室温表示当前子树的根(root)的,也就是当前所在的结点

整理这些题目后我觉得线段树的题目整体上可以分成以下四个部分:

单点更新

最基础的线段树,只更新叶子节点,然后把信息用PushUP(int r)这个函数更新上来

题意:O(-1)
思路:O(-1)
线段树功能:更新:单点增减查询:区间求和

题意:O(-1)
思路:O(-1)
线段树功能:更新:单点替换查询:区间最值

题意:求逆的后最小逆序数
思路:用O(nlogn)复杂度求出最初逆序数后,就可以用O(1)复杂的度分别递推出其他解
线段树功能:更新:单点增减查询:区间求和

题意:H *瓦特的木板,放进一些1 * L的物品,每次是什么意思?放空间能容纳御姐最上边的位子
思路:每次找到最大值的位子,然后减去大号
线段树功能:查询:区间求最大值的位子(直接把更新的操作在查询里做了)

练习

成段更新

通常这对初学者来说是一道坎,需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新或询问到的时候

    • hdu1698只是一个钩子

题意:O(-1)
思路:O(-1)
线段树功能:更新:成段替换(由于只查一次总区间,所以可以直接输出1结点的信息)

    • poj3468整数的简单问题

题意:O(-1)
思路:O(-1)
线段树功能:更新:成段增减查询:区间求和

    • poj2528市长的海报

题意:在墙上贴海报,海报可以互相覆盖,求最后问可以看见几张海报
思路:这题数据范围很大,直接搞超时+超内存,需要离散化:
离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012]我们用不到[-∞,999] [1001,1989] [1991,1999] [2001,2011] [2013,+ ∞]这些值,所以我只需要1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,复杂在于就度大大的降速下来了
所以离散化要保存所有需要用到的值,排序后,分别映射到1〜n的,复杂这样度就会小很多最很多最
而这题的难点在于每个数字其实表示的的英文一个单位长度(并且一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)
给出下面两个简单的例子应该能体现普通离散化的缺陷:
1-10 1-4 5-10
1-10 1-4 6 -10
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于1的话,在其中加上任 一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了。
线段树功能:更新:成段替换查询:简单散列

    • poj3225帮助间隔

题意:区间操作,交,并,补等
思路:
我们一个一个操作来分析:(用0和1表示是否包含区间,-1表示该区间内既包含又包含不含)
U:把区间[l ,r]覆盖成1
I:把[-∞,l](r,∞)覆盖成0
D:把区间[l,r]覆盖成0
C:把[-∞,l)(r,∞]成0,且[l,r]区间0/1互换
S:[l,r]区间0/1互换

成段覆盖的操作很简单,比较特殊的就是区间0/1互换这个操作,可以我们称之为异或操作
很明显我们可以知道这个性质:当一个区间被覆盖后,不管之前有没有异或标记有意义都没了
所以当一个节点得到覆盖标记时把异或标记清空
而当一个节点得到异或标记的时候,先判断覆盖标记,如果是0或1,直接改变一下覆盖标记,不然的话改变异或标记

开区间闭区间只要数字乘以2就可以处理(偶数表示端点,奇数表示两端点间的区间)
线段树功能:更新:成段替换,区间异或查询:简单哈希

练习

    • poj1436水平可见段
    • poj2991起重机
    • 另一个LCIS
    • 支架序列

区间合并

Hust – 【习题索引】线段树,区间合并

这类题目会询问区间中满足条件的连续最长区间,所以俯卧撑的时候需要对左右儿子的区间进行合并

    • poj3667酒店

题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边
2 ab:将[a,a + b-1]的房间清空
思路:记录区间中最长的空房间
线段树操作:更新:区间替换查询:询问满足条件的最左断点

练习:

hdu2871内存控制
hdu1540隧道战
CF46-D停车场

扫描线

这类题目需要将一些操作排序,然后从左到右用一根扫描线(当然是在我们脑子里)过去扫
最解词的就是矩形面积并,周长并等题

    • hdu1542亚特兰蒂斯

题意:面积矩形并
思路:浮点数先要离散化;然后把矩形分成两条边,上边和下边,对横轴建树,然后从下到上扫描上去,用CNT表示该区间下边比上边多几个
线段树操作:更新:区间增减查询:直接取根节点的值

    • hdu1828图片

题意:周长矩形并
思路:与面积不同的地方是还要记录竖的边有几个(numseg记录),并且当边界重合的时候需要合并(用LBD和RBD表示边界来辅助)
线段树操作:更新:区间增减查询:直接取根节点的值

练习

hdu3265海报
hdu3642获取财宝
poj2482你的窗口中的
星星poj2464布朗尼点II
hdu3255农业
ural1707 Hypnotoad的秘密
uva11983奇怪的广告

线段树与其他结合练习(欢迎大家补充)

hdu3333图灵树
hdu3874项链
hdu3016男人下来
hdu3340雨中ACStar
zju3511蛋糕抢劫
UESTC1558慈善交流
CF85-D中位数
sumjs你可以回答这些疑问

发表评论

电子邮件地址不会被公开。 必填项已用*标注