数据结构——线段树——李超线段树

分类: 文章 • 2023-12-16 16:37:22

李超线段树
现在考虑这样一个问题：
动态维护一个平面直角坐标系，支持查询与直线 $x=k$ 相交的线段交点中纵坐标的最大值。
如图，查询结果为绿色直线与 $x=k$ 交点的纵坐标。
插入
记录 $seg(o)$ 表示当覆盖前结点的线段中最优线段的编号