李超线段树
最基础的李超线段树可以做下面的问题：
每次插入若干条直线 \(y=k_ix+b_i\)，查询某个位置 \(x_i\) 上的最值。
考虑一棵线段树结构，在每个节点维护在当前区间中点上的最优直线，当插入一条新直线时：
-
如果该节点为空就把新直线存到当前节点并返回。
-
否则如果新直线在中点处取值比原本的最优直线更优就交换。
-
如果新直线在左端点比原本直线有就递归左区间，右区间同理。
正确性证明：首先第二条保证了新直线在中点位置比原本的最优直线劣，那么如果在左端点也更劣，显然整个左区间都更劣，因此该直线没有用。
- 查询时从询问的点每次往上跳，查询经过的所有直线的最大值即可。
具体实现时可以动态开点，时间复杂度 \(\Theta(n\log n)\)，空间复杂度 \(\Theta(n)\)。
这是一个简洁的写法：
struct segment
{
LL K,B;
int p;
LL operator ()(LL x){return K*x+B;}
}tr[N];
int idx=0;
void Ins(int &k,int l,int r,segment L)
{
if(!k)
{
k=++idx;
tr[k]=L;
return;
}
int mid=(l+r)>>1;
if(L(mid)>tr[k](mid))swap(L,tr[k]);
if(L(l)>tr[k](l))Ins(ls[k],l,mid,L);
if(L(r)>tr[k](r))Ins(rs[k],mid+1,r,L);
}
pair<LL,int> ask(int k,int l,int r,int x)
{
if(!k)return make_pair(0,0);
pair<LL,int> res=make_pair(tr[k](x),tr[k].p);
int mid=(l+r)>>1;
if(x<=mid)res=max(res,ask(ls[k],l,mid,x));
else res=max(res,ask(rs[k],mid+1,r,x));
return res;
}
[模板]李超线段树/[HEOI2013]Segment
插入的从直线变成了线段，把线段拆成 $\log $ 个区间内的直线即可，复杂度 \(\Theta(n\log^2n)\)。
应用
李超线段树最常用的就是解决斜率优化 dp，通常码量小细节少，除了部分卡 \(\log\) 的题，其他情况绝对是第一选择，可以替代大部分 CDQ 优化斜率优化 dp。
「CEOI2017」Building Bridges
可以写出简单的斜率优化式子，可以直接转化成插入直线、查询单点最值，比 CDQ 不知道好写到哪去了。
「SDOI2012」基站建设
道理差不多。
撤销
李超线段树不支持删除，但是显然支持 \(\Theta(\log)\) 的撤销。
CF678F Lena and Queries
除了删除之外和模板一样，套一层线段树分治就可以转化成插入和撤销了。
复杂度 \(\Theta(n\log ^2n)\)。
[CEOI 2009] Harbingers
一样的可以写成斜率优化式子，只不过是从祖先转移的。
在树上 dfs，李超树维护直线，回溯的时候撤销就行了。
广义李超线段树
注意到其实我们没有用到直线的很多性质，因此可以维护的不仅仅是直线，事实上只要该函数满足任意两个函数最多只有一个平凡交点即可。
「POI2011 R1」避雷针 Lightning Conductor
把 \(a_j+\sqrt{i-j}\) 看成函数用李超树维护即可。
可持久化李超线段树
类似普通线段树可持久化就行。
李超线段树合并
类似普通线段树合并，只不过每次要把一个线段树节点的直线插到另一个线段树里。
void Ins(int &k,int l,int r,segment L)
{
if(!k)
{
k=++tot;
seg[k]=L;
return;
}
pushdown(k);
int mid=(l+r)>>1;
if(L(mid)<seg[k](mid))swap(L,seg[k]);
if(L(l)<seg[k](l))Ins(lson[k],l,mid,L);
else if(L(r)<seg[k](r))Ins(rson[k],mid+1,r,L);
}
int Merge(int x,int y,int l,int r)
{
if(!x||!y)return x+y;
pushdown(x);pushdown(y);
Ins(x,l,r,seg[y]);
int mid=(l+r)>>1;
lson[x]=Merge(lson[x],lson[y],l,mid);
rson[x]=Merge(rson[x],rson[y],mid+1,r);
return x;
}
正确性没什么好说的，复杂度据说是 1 个 log，不是很懂。