李超树——倾斜的线段树介绍思想板子
介绍李超树用以解决一种问题:向平面上插入若干条直线(或线段),查询与直线x=a相交线段的交点坐标y的最大值,别看这种问题好像挺个别,很多平面题或DP(斜率优化)的题都可以转换成这种问题,而遇到这种问题,李超树比平衡树好打得多。思想李超树代码看上去和普通线段树非常像,不同的是,每个节点维护的不是的区间,而是两端x坐标为 l、r 的一条带斜率的线段:(注意,每层的线段高低关系不确定,这样画只是为了好看)这样查询只需像线段树那样查就是了,然后怎么插入线段呢?(直线就是 -inf 到 i