本文部分内容借鉴自 OI-WIKI
引入
考虑使用一个数据结构，单次 \(O(\log)\) 地支持以下内容：
插入一个一次函数 \(y_i=k_ix+b_i\)。
对于一个 \(x_0\)，找到一个最大的 \(y_i=k_ix_0+b_i\)，其中 \(1\le x_0 \le n\)。
容易发现，常规 \(O(\log)\) 的数据结构，如线段树、树状数组等无法很好地维护此内容，于是我们考虑一个新的数据结构来支持这些内容地维护。
做法
李超线段树具有普通线段树都有的树状结构，每个节点代表一个区间 \([l,r]\)。
插入
考虑插入一条直线 \(f_i\)：
- 若当前节点没有线段，将当前节点的标记标为 \(l_i\) 并返回。
- 若当前节点有直线 \(f_j\)：
- 若 \(f_i(mid)\)
查询
假设我们已经维护好了上述内容，则查询 \(x\) 时我们只需从李超线段树的根一路查询到 \([x,x]\) 对应的节点即可。由树高 \(O(\log n)\) 可知，单次查询复杂度 \(O(\log n)\)。
拓展
如果插入的是线段，我们只需在线段定义域对应的 \(O(\log n)\) 个区间中进行上述的插入步骤即可，时间复杂度 \(O(\log ^2 n)\)。
愿此行，终抵群星。