李超树是线段树的一种实际应用，能够动态维护二维直角坐标系中的若干条线段 $y = k x + b, \ x \in S$ 在 $x$ 的某个取值 $x_0$ 处的最值。
基本思想
考虑暴力解决这个问题，每次遍历 $n$ 条线段找到最大值，单次复杂度是 $O(n)$ 的。而李超线段树的核心思想就是去掉不可能的结果，缩小遍历的范围，从而达到更低的复杂度。
对于在权值线段树上的修改操作，神仙 tommy 的博客讲的很🐮，这里引用一下：
维护区间内可能成为最优解的线段，且保证时间复杂度就成了这个算法的核心问题。对于这一问题，我们可以使用斜率和线段在当前区间中点上的取值，进行分类讨论。这里就以求最大值为例进行分析。
- 若当前区间内没有任何线段，则直接将新线段放入当前区间。
若当前区间 $[l, r]$ 内有旧线段，且新线段的斜率大于旧线段的斜率，设当前区间中点为 $m$：
若旧线段在 $m$ 上的取值大于新线段在 $m$ 上的取值，则新线段在 $[l, m]$ 上的取值一定不比旧线段更优，但新线段在 $[m + 1, r]$ 上的取值可能更优，将新线段下放至 $[m + 1, r]$ 区间并递归更新答案。
若旧线段在 $m$ 上的取值小于新线段在 $m$ 上的取值，则旧线段在 $[m + 1, r]$ 上的取值一定不比新线段更优，但旧线段在 $[l, m]$ 上的取值可能更优，用新线段替换该当前节点的旧线段，将旧线段下放至 $[l, m]$ 区间并递归更新答案。
若当前区间 $[l, r]$ 内有旧线段，且新线段的斜率小于旧线段的斜率，设当前区间中点为 $m$：
若旧线段在 $m$ 上的取值小于新线段在 $m$ 上的取值，则旧线段在 $[l, m]$ 上的取值一定不比新线段更优，但旧线段在 $[m + 1, r]$ 上的取值可能更优，用新线段替换当前节点的旧线段，将旧线段下放至 $[m + 1, r]$ 区间并递归更新答案。
若旧线段在 $m$ 上的取值大于新线段在 $m$ 上的取值，则新线段在 $[m + 1, r]$ 上的取值一定不比旧线段更优，但新线段在 $[l, m]$ 上的取值可能更优，将新线段下放至 $[l, m]$ 区间并递归更新答案。
- 若当前区间 $[l, r]$ 内有旧线段，且新旧线段斜率相同，比较截距 $b$，截距大的线段在 $[l, r]$ 上的取值一定优于截距小的线段，直接用截距大的替换截距小的。
可以通过标记永久化实现。可以证明，查询和全局修改的复杂度是 $O( \log n)$，区间修改的复杂度是 $O( \log^2 n)$，不过常数好像很小？
其实这篇博文是个板子存放处
模板
[JSOI2008]Blue Mary开公司 - 全局修改 & 全局单点查询
由于我的线段树是预处理区间左右端点的，全局操作变得异常好写（