引入与概括
思考下列问题：
在平面直角坐标系中维护集合，支持下列操作：
-
加入一个定义域为 \([l,r]\) 的一次函数。
-
查询所有定义域包含 \(x\) 的一次函数的函数值的最值。
我们发现，这可以看成一个区间修改，单点查询的问题，考虑使用线段树维护。
但我们发现传统线段树难以维护，于是李超线段树应运而生。
李超线段树常用于 DP 优化（斜率优化），常数小，代码复杂度小。
李超线段树是一种值域线段树，当值域过大无法承受时可以 离散化 / 动态开点。
具体实现
在线段树的每一个节点维护当前区间可能成为最优解的线段（也就是一次函数，二者可以转化），即该线段在区间的某个取值上有最优解。
查询时只需要遍历 \(O(\log n)\) 个节点即可找出最优解，时间复杂度为 \(O(\log n)\)，插入直线（定义域包含整个值域的线段）时时间复杂度为 \(O(\log n)\)，插入线段时时间复杂度为 \(O(\log^2n)\)。
- 简单处理（以维护最小值为例）
struct Line{//每一条直线用斜截式 k,b 表示
int k,b;
}line[N];
int calc(int id,int x){//对应给定线段和横坐标计算纵坐标
return x*line[id].k+line[id].b;
}
bool Less(int id1,int id2,int x){//比较线段的函数值
return calc(id1,x)<calc(id2,x);
}
- 插入
插入直线：
void add(int p,int l,int r,int id){
if(!a[p]){a[p]=id;return ;}
if(l==r){if(Less(id,a[p],l)) a[p]=id;return ;}
if(Less(id,a[p],mid)) swap(a[p],id);
if(Less(id,a[p],l)) add(p<<1,l,mid,id);
if(Less(id,a[p],r)) add(p<<1|1,mid+1,r,id);
}
插入线段：
void add(int p,int l,int r,int x,int y,int id){//先找到线段对应的区间再按直线的方式插入
if(x<=l&&r<=y){
if(!a[p]){a[p]=id;return ;}
if(l==r){if(Less(id,a[p],l)) a[p]=id;return ;}
if(Less(id,a[p],mid)) swap(a[p],id);
if(Less(id,a[p],l)) add(p<<1,l,mid,x,y,id);
if(Less(id,a[p],r)) add(p<<1|1,mid+1,r,x,y,id);
return ;
}
if(x<=mid) add(p<<1,l,mid,x,y,id);
if(y>mid) add(p<<1|1,mid+1,r,x,y,id);
}
- 查询
查询函数值：
int query(int p,int l,int r,int x){
int res=calc(a[p],x);
if(l==r) return res;
if(x<=mid) res=min(res,query(p<<1,l,mid,x));
else res=min(res,query(p<<1|1,mid+1,r,x));
return res;
}
查询函数值对应线段：
int query(int p,int l,int r,int x){
if(l==r) return a[p];
int res=0;
if(x<=mid) res=query(p<<1,l,mid,x);
else res=query(p<<1|1,mid+1,r,x);
return Less(a[p],res,x)?a[p]:res;
}