李超线段树

李超发明的一种维护平面上有限值域的直线或线段纵坐标大小的一种数据结构。

因为是根据线段树研发的，代码也基于线段树，所以叫李超线段树。

常规支持：

• 插入一条线段或直线。
• 查询单点最大的直线或线段上的纵坐标

查询通俗一点讲就是：给一堆直线和线段，求从一个横坐标的正无穷高往下做一条直线与给定的一堆直线和线段的首个交点的纵坐标位置。

插入一条直线的时间复杂度为 \(O(\log n)\)，插入一条线段的时间复杂度为 \(O(\log^2 n)\)。\(n\) 为要维护的值域，直线可以理解为横跨整个值域的线，线段则是不横跨整个值域的线。

插入直线，具体插入的过程是：

对于当前处理到的区间，维护最优直线表示在当前区间的中点纵坐标最大的直线（初始相当于一条 \(y=-\infty\) 的直线），然后跟新插入的直线比较，有 \(3\) 种情况：

• 最优直线完全压制新插入直线：放弃插入。

• 新插入直线完全压制最优直线：把当前最优线段改为新插入直线，返回。

• 新插入直线与最优直线在此区间内有相交：新插入直线为当前区间的最优直线，而把旧的区间最优直线继续下传，下传区间为此 2 条直线相交的那边区间。

对于第三个操作，要想理解其原理（为什么要交换线段下传），就得把查询操作也说了。

查询某个点的最大纵坐标，把线段树二分找这个点过程中经历的 \(\log n\) 个区间的最优直线在这个点的取值取 \(\max\)，即为答案。

为什么这样做是对的？因为如果不在这些直线上，就一定存在一条直线在这个点的取值比这些直线在这个点的取值都大，那这条直线在插入时至少会有一个区间的中点为当前查询的点（最坏就是线段树的叶子，区间就为这个点时），此时这条直线一定会成为这个区间的最优线段。而它没成，所以推出矛盾，所以不存在这条直线。

然后就可以解释为什么上述的第 3 种情况要交换区间最优和当前插入直线，因为在区间最优赋值为当前插入直线时，再下面再赋值成这条线段已经没必要了，对于每次查询来说结果是一样的。而被替换下来的以前最优在子树内还有可能是优秀的，所以要递归下去。为什么要往交界点的那边区间递归？因为只有交界点那边的这条被压制的直线才可能反压制，而另一边肯定被压制得更狠。（可以自行画图，就 2 种情况，交界点在左或交界点在右。）

对于插入线段，可以看做找到线段树的极大区间满足这条线段在这个极大区间内可以看做直线，再用插入直线的方法递归下去。找这些极大区间的过程，类似于线段树的区间查询，最多分成 \(\log n\) 个区间，而每个区间都要递归到底，又是一个 \(\log n\)，所以插入线段的时间复杂度为 \(\log^2 n\)。

代码待会补。我现写。

例题也会更新。