李超线段树

· · 算法·理论

P4097 【模板】李超线段树 / [HEOI2013] Segment。

维护平面坐标系,支持 q 次操作:

  • 给定 k,b,l,r,插入线段 f(x)=kx+b,x \in [l,r]。
  • 给定 x_0,求 x_0 \in [l_i,r_i] 的 f_i(x_0) 取到 \max 的 i。

强制在线。

插入线段,查询单点最值可以使用李超线段树维护。

对 x 轴维护线段树。称区间 [l,r] 内的最优线段为,定义域 \subseteq [l,r] 且与 m=\frac{l+r}{2} 交点取 y_{\max} 的线段。李超树维护每个节点的最优线段,查询时直接递归即可。

对于修改,我们将插入线段 [l_0,r_0] 和最优线段进行讨论:

修改时李超树始终保持单侧递归,复杂度 O(q \log^2 n)。

李超树可以视作一种特殊的单侧递归线段树,最优线段是标记永久化的体现。

最优线段构成线段集合的包络线,对偶后维护的就是点集的凸包。因此李超树的本质是动态凸包。

P10980 任务安排 4.1

李超树维护斜率优化 DP。

设 a_i 为 T_i 的前缀和,b_i 为 C_i 的前缀和。容易列得朴素 DP

f_i \gets f_{j-1}+a_i(b_i-b_{j-1})+s(b_n-b_{j-1}) ,\quad j\le i

其中 f_i 表示仅考虑前 i 个任务的最小代价,枚举上一个划分点 j。最后 +s(b_n-b_{j-1}) 提前计算后面所有任务的代价。

不妨令 j \gets j-1 开始推式子

\begin{aligned} f_i &\gets f_{j}+a_i(b_i-b_{j})+s(b_n-b_{j})\\ &= f_j+a_ib_i-a_ib_j+b_ns-b_js\\ &= -b_ja_i+(f_j-b_js)+(a_ib_i+b_ns) \end{aligned}

问题可以视作,插入直线 -b_jx+(f_j-b_js),在 i 处查询 x=a_i 的 y_{\min}。可以使用李超线段树优化,复杂度 O(n \log n)。