李超树是一种特殊的线段树，据说由杭州学军中学的李超提出。他支持查询一个区间中许多条形如\(y=kx+b\)的直线中的最小/最大点的位置。下文中默认查询的是最大值，最小值同理。
李超树的每一个节点\(p\)维护了在当前区间\([l,r]\)中在最上方看时最长的一条线段。实际上，在跨过这个区间的许多线段中只有这一条会在这整个区间中发挥作用。
如果还没有理解，看下面的图：
在上图中，蓝线是原来区间中存储的直线，橙线是新加入的线。
观察得到，橙线在上方，可以对答案做出贡献的部分横跨过了左右子区间；而蓝线在被橙线盖上一大段之后只在右半的区间中才能对答案最大值做出贡献。递归比较，最后只有一条线在最上方的部分跨过了左右子区间，进而只用维护这一条线。
插入一条线时，如果当前区间的两条线没有交点则直接只保留在上方的那一条，否则按照上面的方法留下一条横跨左右的线，然后把另一条线插入其所在的子区间里即可。这样，复杂度即可控制在\(\log n\)。
在查询一个区间的最值时，要一直递归访问到最下面，才可以保证找到了真正的最值。
模板例题即为bzoj1568，代码写完了再补
参考资料：https://blog.csdn.net/roll_keyboard/article/details/81127266