李超线段树学习笔记

李超树是一种用来维护直线的数据结构，可以在 $O(\log V)$ 的时间复杂度内求出所有直线中在 $x=k$ 处的最大 $y$ 取值。

考虑用线段树去维护这个东西，可以让每个节点维护在它的区间中点 $x=mid$ 处 $y$ 最大的直线，每新插入一条直线时，若这条直线在 $x=mid$ 处的 $y$ 取值比 $u$ 上之前的直线小，那么分两种情况：

• 当前直线的斜率 $k'$ 大于之前直线的斜率 $k$，此时这条直线往左走肯定比 $u$ 上之前的直线低，那么只能往右走，所以递归插入右儿子；
• 当前直线的斜率 $k'$ 小于之前直线的斜率 $k$，此时这条直线往右走肯定比 $u$ 上之前的直线低，那么只能往左走，所以递归插入左儿子；

否则若这条直线在 $x=mid$ 处的 $y$ 取值大于等于 $u$ 上之前的直线，那么更新 $u$ 上的直线，并且把之前 $u$ 上的直线往下插入。

查询 $k$ 时不断在线段树上往 $k$ 递归，把路径上的线段在 $x=k$ 处的取值取个 $\max$ 即可，正确性显然。

注意每个节点的直线要初始化为 $y=0x+(-\infin)$。

代码如下：

struct node
{
	int k,b;
	inline int slove(int x) {return k*x+b;}
}mx[S<<2];

inline void built(int u,int l,int r)
{
	mx[u].k=0;
	mx[u].b=-1e8;
	if(l==r) return;
	int mid=l+r>>1;
	built(u<<1,l,mid),built(u<<1|1,mid+1,r);
}

void ins(int u,int l,int r,node val)
{
	if(l==r) return void(mx[u]=(val.slove(l)>mx[u].slove(l)?val:mx[u]));
	int mid=l+r>>1;
	int pre=val.slove(mid);
	if(pre>mx[u].slove(mid)) swap(val,mx[u]);
	if(val.k>mx[u].k) ins(u<<1|1,mid+1,r,val);
	else ins(u<<1,l,mid,val);
}

int que(int u,int l,int r,int x)
{
	if(l==r) return mx[u].slove(x);
	int mid=l+r>>1;
	if(x<=mid) return max(mx[u].slove(x),que(u<<1,l,mid,x));
	else return max(mx[u].slove(x),que(u<<1|1,mid+1,r,x));
}