李超树学习笔记

· · 算法·理论

李超树学习笔记

李超树是一种维护区间最优线段/直线的线段树。

称一条线段能成为区间 [l,r] 中的最优线段 ，当且仅当：

核心思想：标记永久化！只需满足包括单点的所有线段树区间“最优线段”中含有该单点的最优线段即可，依此保证复杂度

考虑插入一条线段时如何更新如何更新：（可以画个图理解一下）

如果新线段斜率大于原线段，

如果新线段斜率小于原线段，

另一种更简洁的实现：将新直线 f 与原有直线 g 在中点处的取值进行比较，若新线段较优，交换 f,g，以下只考虑 f 不如 g 优的情况

模板题

P4097 [HEOI2013]Segment

本题要求维护区间最优线段，我们按上面所说的模拟即可。考虑复杂度，我们将线段分割到 \log n 个区间，每个区间又要用 \log n 的时间更新它及它的子区间，总复杂度为 O(n\log ^2n)。

本题易挂点：注意特判 x0==x1 的情况；坐标相同时取标号小的。

P4254 [JSOI2008]Blue Mary开公司

本题中插入的是直线 ，所以不需要将线段分割到其对应的区间，直接更新即可。复杂度 O(n\log n)。

李超树维护一次函数

其实就是维护直线/线段。但因为这道题不算很板，所以单独开个分类。

P4069 [SDOI2016]游戏

进行第一个操作时，我们可以把路径拆为两部分

操作二：维护区间最小值，包含在询问区间内部的节点直接返回最小值，路径上经过的节点取其最优线段在本区间内的最小值（端点处）作为标记，和左、右儿子中的答案去 \min

还有一些实现上的细节见代码注释。

李超树维护斜率优化

这部分很大程度上参考了 @panyf 巨佬的博客，在这里orz！

若 dp 式子可化为 f_i=\min(k_jh_i+b_j)+a_i 的形式，我们可以用斜率优化降低复杂度。问题转化为，插入直线 y_j=k_jx+b_j，求 x=h_i 处 y 的最小值。与单调队列维护凸包相比，用李超树维护不需要 k,x 单调，理解也更直观。

对于 x 值域较大或为小数的情况，可将 x 先离散化再建树，或动态开点并在 r-l<eps 时 return

P4655 [CEOI2017]Building Bridges

设 sum_i 为 w 的前缀和，容易推出朴素 dp 式子：

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

稍作化简得： f_i=h_i^2+sum_{i-1}+\min(-2h_jh_i+h_j^2-sum_j+f_j)

设 a_i=-2h_i,b_i=h_i^2-sum_i+f_i，则f_i=h_i^2+sum_{i-1}+\min(a_jh_i+b_j)

问题转化为，插入直线 y_j=a_jx+b_j ，求 x=h_i 时 y 的最小值。 直接用李超树维护即可。

代码细节：一定要给 b_0 赋初值！

P4027 [NOI2007]货币兑换

首先要注意到一个关键性质：必然存在一种最优的买卖方案满足每次买进操作使用完所有的人民币，每次卖出操作卖出所有的金券。（其实这个性质就写在题面最下方）

设 f_i 为第 i 天最多拥有的钱数，x_i 为第 i 天用 f_i 元钱可以兑换的 A 券数，y_i 为 B 券数。 可列出方程

可得：

\left\{ \begin{aligned} & x_iA_i+y_iB_i=f_i \\ & \frac{x_i}{y_i}=R_i \\ \end{aligned} \right.

解方程得 x_i=\dfrac{f_iR_i}{A_iR_i+B_i}，y_i=\dfrac{f_i}{A_iR_i+B_i}

若第 i 天不卖出，那么 f_i=f_{i-1}；若卖出，f_i=\max(A_ix_j+B_iy_j)，变形得 f_i=\max B_i(\frac{A_i}{B_i}x_j+y_j)。设k=x_j,b=y_j,x=\frac{A_i}{B_i}，那么 f_i=\max B_i(kx+b)。用李超树维护即可。

但是 \frac{A_i}{B_i} 不是整数怎么办呢？直接离散化即可！

CF932F Escape Through Leaf

一个显然的 dp 式子： f_u=f_v+a_u\times b_v 。这个式子一看就很李超树！但是是个树上问题，所以我们需要李超树合并！合并时的具体操作即合并两个节点的标记，将 y 节点的最优直线插入 x。虽然感性理解这么做的复杂度为 O(n\log^2n) 的，但由于每次都会导致一条直线在线段树中的深度增加，直线总深度 O(n\log w)，李超树合并的复杂度为 O(n\log w)。

P2305 [NOI2014]购票

先丢个朴素的 dp 式子 f_u=\min(f_{fa}+(dis_u-dis_{fa})\times p_u+q_u)

稍微推一下得 f_u=dis_up_u+q_u+\min (f_{fa}-dis_{fa}p_u)。

如果 t=0，就是李超树板子题。加上 l 的限制，我们可以用线段树套李超树。但我们实际上要维护一条树链的信息，所以可以再套个树剖，复杂度为 O(n\log^3n) 。

但更好的做法是利用出栈序，也就是每个结点离开 dfs 的顺序 。（再次sto @panyf 巨佬 orz！）下面引用一段他的博客。

直接在点 i 及其最远的满足 d_i-d_j\leq l_i 的祖先 j 的出栈序对应的区间上查询。容易发现区间内不在 i 和 j 的路径上的点都未被访问到，不会对答案产生贡献。这样就不需要树链剖分了。时间复杂度 O(n\log^2n) n)，空间复杂度 O(n\log n)。

但因为树剖的常数很小，李超树常数又很大，所以树剖的 O(n\log^3n) 做法和这种理论更优解实际跑出来的时间差不多。

再扔几个例题

其实基本上所有的斜率优化题都可以用李超树做，但是比单调队列多个 log（和很大的常数）。于是我现在看到斜率优化题就想用李超树，真的比单调队列好想好写多了！