浅析李超线段树及其应用

算法思想及实现

一种高级数据结构,最经典的应用就是维护一个二维平面直角坐标系,支持动态插入线段,询问与直线$x=x_0$相交的已插入线段中交点y的最大/最小值,即当$x=x_0$,求$max${$k_ix+b_i$}或$min${$k_ix+b_i$}。两种情况本质上是一样的,那我们现在就来讨论一下它的实现。

解决这个问题,最暴力的做法就是当$x=x_0$时,将n条线段全部遍历一遍,时间复杂度为$O(n)$,这似乎就是这个问题的瓶颈了,那么如何优化时间复杂度呢?这种做法给了我们启发,这个问题的瓶颈就在于需要遍历的集合过大,那么,如果找到一种方法能够有效减小集合大小,排除不可能成为最优解的,是否就能够降低时间复杂度呢?答案是肯定的。李超线段树使用的正是这种思想。

李超线段树是一种特殊的线段树,它的特殊之点在于每个区间只记录在当前区间可能成为最优解的线段,即该线段在当前区间的某个取值上有最优解。可以证明当查询的时候,只需要遍历$ \log n$个节点,即可找出最优解,故单次查询时间复杂度为$O(\log n)$。修改时通过替换和下放线段,可以达到$O(\log n)$的时间复杂度。

维护区间内可能成为最优解的线段,且保证时间复杂度就成了这个算法的核心问题。对于这一问题,我们可以使用斜率和线段在当前区间中点上的取值,进行分类讨论。这里就以求最大值为例进行分析。

  1. 若当前区间内没有任何线段,则直接将新线段放入当前区间。

  2. 若当前区间$[L,R]$内有旧线段,且新线段的斜率大于旧线段的斜率,设当前区间中点为$mid$:

  • 若旧线段在$mid$上的取值大于新线段在$mid$上的取值,则新线段在$[L,mid]$上的取值一定不比旧线段更优,但新线段在$[mid+1,R]$上的取值可能更优,将新线段下放至$[mid+1,R]$区间并递归更新答案。

  • 若旧线段在$mid$上的取值小于新线段在$mid$上的取值,则旧线段在$[mid+1,R]$上的取值一定不比新线段更优,但旧线段在$[L,mid]$上的取值可能更优,用新线段替换该当前节点的旧线段,将旧线段下放至$[L,mid]$区间并递归更新答案。

  1. 若当前区间$[L,R]$内有旧线段,且新线段的斜率小于旧线段的斜率,设当前区间中点为$mid$:

    • 若旧线段在$mid$上的取值小于新线段在$mid$上的取值,则旧线段在$[L,mid]$上的取值一定不比新线段更优,但旧线段在$[mid+1,R]$上的取值可能更优,用新线段替换当前节点的旧线段,将旧线段下放至$[mid+1,R]$区间并递归更新答案。
    • 若旧线段在$mid$上的取值大于新线段在$mid$上的取值,则新线段在$[mid+1,R]$上的取值一定不比旧线段更优,但新线段在$[L,mid]$上的取值可能更优,将新线段下放至$[L,mid]$区间并递归更新答案。
  2. 若当前区间$[L,R]$内有旧线段,且新旧线段斜率相同,比较截距$b$,截距大的线段在$[L,R]$上的取值一定优于截距小的线段,直接用截距大的替换截距小的。

如何理解通过两条线段在$mid$上的取值和线段的斜率就能确定哪条线段更优?我们可以通过旋转来理解。

rotate.jpg

设$y_1$为旧线段,$y_3$为新线段,$mid$为当前区间$[L,R]$的中点,这里以$y_1$的斜率大于$y_3$且$y_1$在$mid$上的取值大于$y_3$为例。设线段$y_2$与线段$y_1$斜率相同,且在$mid$上的取值与$y_3$在mid上的取值相同,可以发现$y_2$在$[L,mid],[mid+1,R]$上的取值一定不比$y_1$更优。还可以发现,当我们将$y_2$向逆时针旋转$\beta^{\circ}(0^{\circ}<\beta^{\circ}<\alpha^{\circ})$时,$y_2$的斜率逐渐变小,在这过程中$y_2$与$y_1$在$[L,mid]$有交点且$y_2$在$[L,mid]$的取值整体变大,说明$y_2$在$[L,mid]$区间内可能存在某个取值使$y_2$成为最优解;而在这过程中,$y_2$在$[mid+1,R]$上的取值整体变小,一定不会成为最优解。易证将$y_2$向逆时针旋转$\beta^{\circ}(0^{\circ}<\beta^{\circ}<\alpha^{\circ})$得到的$y_2’$中,一定存在某个$y_2’$与$y_3$完全相同,故$y_2$变化趋势即为$y_3$变化趋势。

另外,经过观察,可以发现分类讨论的框架与线段树很相似,可以直接放到线段树上维护,这就是李超线段树。

例题

Luogu P4254/P4097 Blue Mary开公司/Segment

这是江苏2008年的省选题/河北2013年的省选题(省选居然考板子题

除了一些细节需注意以外,这两题很明显是个李超线段树的裸题,就直接上 P4252 的代码了。

Luogu P4069 [SDOI2016]游戏

题目简述

  • 一棵$n$个点的树,有$n-1$条边,边有边权。
  • 每次会选择一条路径$u$->$v$,给出$a$,$b$,设路径上任意一点与$u$的距离为$dis$,将路径上每一点的权值设为$a*dis+b$。
  • 或者选择一条路径$u$->$v$,求该路径上的最小点权。
  • 这样的操作共有$m$个,初始时树上所有点的权值均为$123456789123456789$(为啥不是114514)

强行上树差评

这题挺简单的,树剖剖一剖,将树上问题转化为序列问题,就可以用李超线段树来做了。

但需要注意,李超线段树只能维护k值确定的线段,所以我们要将式子适当变形,然后直接在李超线段树上维护区间最值就可以了。

P4655 [CEOI2017]Building Bridges

题目简述

有 $n$ 根柱子依次排列,每根柱子都有一个高度。第 $i$ 根柱子的高度为 $h_i$。

现在想要建造若干座桥,如果一座桥架在第 $i$ 根柱子和第 $j$ 根柱子之间,那么需要 $(h_i-h_j)^2$ 的代价。

在造桥前,所有用不到的柱子都会被拆除,因为他们会干扰造桥进程。第 $i$ 根柱子被拆除的代价为 $w_i$,注意 $w_i$ 不一定非负,因为可能政府希望拆除某些柱子。

现在政府想要知道,通过桥梁把第 $i$ 根柱子和第 $j$ 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

分析&解答

很明显,如果没有最后一句话,这道题不可做。

但是,规定了不可能在端点外任何地方相交,一定是线性的,很明显想到DP。

设$f_i$为将第$1$根和第$i$根柱子相连的代价,则有状态转移方程:

$f_i=\min{f_j+\sum_{k=j+1}^{i-1} w_k + (h_i-h_j)^2}$

我们可以令$sum_i=\sum_{k=1}^{i} w_k$ ,这样就可以将 $\sum_{k=j+1}^{i-1} w_k $写作$sum_{i-1}-sum_j$,得:

$f_i=\min{f_j+sum_{i-1}-sum_j+ (h_i-h_j)^2}$

展开$(h_i-h_j)^2$得:

$f_i=\min{f_j+sum_{i-1}-sum_j+ h_i^2-2h_ih_j+h_j^2}$

整理可得:

$ f_i=\min{(-2h_ih_j+f_j-sum_j+h_j^2)+(sum_{i-1}+ h_i^2)} $

看上去是不是很像斜率优化DP的样子?但是我不会

这既然是李超线段树的例题,当然要用李超线段树啦( 路人:我信了你的鬼逻辑,你能够动态维护这一堆乱七八糟的式子我把屏幕吃了

观察一下可以发现,若 $i$ 确定,$(sum_{i-1}+ h_i^2)$为常数项,可以忽略。

于是就变成了对于一个确定的 $i$ ,求$\min{-2h_ih_j+f_j-sum_j+h_j^2} $

很明显的,这是一个类似于$\min{kx+b}$的式子,事实上它的值可以用李超
线段树求出来。

将$-2h_j$看作$k$,则对于每一个$k$,都有 $f_j-sum_j+h_j^2$ 与之对应,
很明显这就是求$i-1$个一次函数在$h_i$上的取值最小,可以在转移过程中使
用李超线段树维护这个值,从而达到$O(n \log n)$的时间复杂度。

总结

李超线段树是一种基于线段树维护一次函数在值域上维护最值的$log$级数据结构,多用于一些最优性问题,但主要用途是用来优化DP,从而绕开繁琐的斜率优化DP推导过程以及维护凸壳。

在DP优化中使用李超线段树能够显著减少码量,提升代码可读性,常数和线段树常数一样(这不废话么

缺点是对于一些斜率优化DP有所局限,不能完全适用。但是根据题目的性质合理使用,一定能给你的做题带来良好体验(大雾

Tagged with:

发表评论