线段树及其扩展
线段树是一种维护区间性质,满足符合结合律的运算的区间修改的数据结构。
基本实现
朴素线段树
|
|
查询与修改代码类似,三步
- 查询(修改)区间与当前区间无交集,直接返回
- 当前区间完全被包含在查询(修改)区间内,对当前树节点(和懒标记)修改或直接返回当前树节点
- 当前区间与查询(修改)区间有交集,下推懒标记后递归处理左右儿子。
双tag线段树
有两种操作,需要两个懒标记,需要定义优先级。注意两种操作对值的影响和先后顺序,并且做出修改。
|
|
jls线段树
同时维护两个值,在修改时比较两个值,如果修改不会影响结果则直接退出,否则分类讨论修改区间和。
|
|
动态开点线段树
在需要用到左右儿子的时候再分配下标,在push_down(或update反正是修改时)中开点。
|
|
由于不用build,而是在修改过程中建树,所以建的位置需要记录,所以update中传入了引用,为了在函数中改变值。
权值线段树
开桶保存每一个数出现的次数,用线段树去维护桶即为权值线段树。由于需要按值域去开数组,所以常常动态开点。可以 $O(logv)$ ( $v$ 为值域)地查询某个范围内的数出现的总次数。不仅如此,它还可以 $O(logv)$ 地求得第 k 大的数。
|
|
zkw线段树
非递归式线段树,把线段树开成满二叉树,从叶子结点往上处理,缩小传统线段树的常数与代码量。无法处理有运算优先级的问题,如双tag。
|
|
主席树(可持久化权值线段树)
为了保存每一次的历史记录,每次修改实际上是新建了一棵线段树,并不对原树做任何修改。但为了合理的时空复杂度,可以发现每次修改只会改一部分结点,剩下的结点可以共用。因此可持久化只需要把修改改为动态开点,只新建需要修改的点。每次修改都会新增一个根节点,因此查询时需要选择查询哪个根节点。 在建立第一个版本的线段树时应当一次建好,之后再动态开点。 虽然我不喜欢用一堆宏,但是这里不用宏代码会显得逻辑不够清晰且啰嗦冗余,所以算了。
单点修改
|
|
区间修改
使用标记永久化技术,即不再向下传递标记,而是查询时带着标记。
|
|
求静态区间第k小数
摘自算法学习笔记(50): 可持久化线段树 - 知乎 先建立一棵全0的树(因为要可持久化所以不能动态开点):
|
|
把原数组离散化:
|
|
然后按原区间中的顺序,把离散化后的数据一个一个地插入可持久化的权值线段树:
|
|
重点来了:我们已经有了求[1, r]内第k小数的方法(查询相应历史版本即可),而求[l, r]内第k小数,只需对kth函数稍作修改。注意,我们在求kth时会用到当前左儿子对应的区间和,现在要排除[1, l-1],那么把这部分和减去即可。
|
|
李超线段树
一种用于维护平面直角坐标系内线段关系的数据结构。(也许计算几何能用?某年icpc出到了可以用这个做)
基本应用
线段树染色问题
-1表示染了多种颜色,0表示未染色,其它数字表示颜色种类。
似乎只要用父节点和懒标记的值区间覆盖就行了。
修改时要考虑下递归之后的回溯,对于两个子区间的颜色是什么情况来更新父区间的颜色情况。
查询时对于一个区间内颜色的情况,未染色直接返回,染了多种颜色则递归查。跨区间的也递归查。
扫描线
经典应用,解决平面矩形覆盖的面积和问题。(也能够扩展到空间和其它图形)。
思想是水平或竖直方向扫描,以下以水平方向扫描为例,也就是矩形的竖边作为扫描线。从左往右扫,将整个图形分成若干个小矩形相加(如果上下两个矩形分开,视为合并在一起的就好)。那么,扫过的距离就是小矩形的宽,只有长在不断变化。使用线段树维护扫过区间内被覆盖的次数和长度,然后相乘即可。
具体思路如下:首先按照边来读入,对左边的边标记为1,右边的标记为-1,然后离散化,使用二分来查找对应的边。建立线段树,其中的每一个点表示一条线段,维护该线段的长度len与被多少个矩形覆盖的cnt。按照每一条边去更新线段树,每更新一条边在答案上累加。(扫描线)最后输出答案即可。
|
|