李超线段树

参考资料

• 李超线段树 - OI Wiki

简介

李超线段树 维护一组一次函数（线段），支持插入一条线段、查询某个横坐标处所有线段取值的最大（或最小）值。

每个节点记录「在该区间中点处最优」的那条线段；插入时与节点上已有线段比较，把较劣的一条递归下放到它仍可能更优的半区间。插入复杂度 $O(\log^2 n)$，单点查询 $O(\log n)$。它常用作斜率优化的替代，尤其当斜率与查询点都不单调时。

例题

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

在平面上在线维护若干条线段，支持两种操作：加入一条线段；查询所有线段中，在给定横坐标处纵坐标最大的线段编号。