[数据结构与算法]从零开始的数据结构：李超线段树

在平面上加入一条线段。记第 i 条被插入的线段的标号为 ，该线段的两个端点分别为$(x_0,y_0),(x_1,y_1)$ 。
给定一个数 k ,询问与直线 x=k 相交的线段中，交点纵坐标最大的线段的编号（若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段）。特别地，若不存在线段与给定直线相交，输出 0;

对于上面这个问题普通的线段树并不好解决，这时就需要李超线段树。

李超线段树

我们像线段树一样建立节点，每个节点维护一个（该区间较大范围的优势线段，不一定全局最优）直线信息。

现在我们假设在一个区间里要插入一条直线就有以下几种情况：
ps:以下插入的直线为$ins$(绿色)，原来的直线为$now$（红色）;

1.这个区间还没有过线段，直接更新最大线段为插入线段即可。

2.$ins$两端的端点都比$now$两端的端点低，这种情况就可以直接返回，因为这样$ins$这条线段永远不会比$now$更优。

3.$ins$两端的端点都比$now$两端的端点高，这种情况就直接修改这个区间的最高直线(把$now$更新成$ins$)就可以返回了。

4.剩下两端点不一致的要特殊判断:
①$ins$的左端点大于$now$的左端点,$ins$的右端点小于$now$的右端点，而且两条线段的交点在区间中值的左边。

②$ins$的左端点大于$now$的左端点,$ins$的右端点小于$now$的右端点，而且两条线段的交点在区间中值的右边。

③$ins$的左端点小于$now$的左端点,$ins$的右端点大于$now$的右端点，而且两条线段的交点在区间中值的左边。

④$ins$的左端点小于$now$的左端点,$ins$的右端点大于$now$的右端点，而且两条线段的交点在区间中值的右边。

总结来看：李超线段树就是用标记永久化维护平面内线段覆盖情况的线段树。和线段树不一样的事，当前节点维护的直线不一定是最好的，而是相对能覆盖更大区域的一个优势线段，因此查询的时候一定要递归到底。

接下来是代码实现部分 (看下面就行了)
我们知道对于一条直线可以表示成 $kx+b=y$所以只要记住k和b我们就能表示一条直线。
然后就是上面提到的中点，有两种算法：

1.下面直接算两条直线的交点，然后和中点比较
2.算两条直线中点的y来比较。

主要还是自己画下图会更明白点。

#define line pair<double,double>//第一个表示K,第二个表示B
double f(line x,int X)//计算kx+b 
{
	return x.first*X+x.second; 
}
double inter(line x,line y)//计算交点位置
{
	return (y.second-x.second)/(x.first-y.first); 
}

然后是更新操作，看懂上面的情况分析基本没什么难度

int tot;//计数器
line li[N];//记录直线信息
int tree[N<<2];//表示这个节点的可能的最优线段
void update(int now, int l, int r, int k, int L, int R)
{
	int mid = (l + r) >> 1;
	if (L <= l && r <= R)
	{
		if (!tree[now])//第一种情况
		{
			tree[now] = k;
			return;
		}
		double ly1 = f(li[k], l), ry1 = f(li[k], r), ly2 = f(li[tree[now]], l), ry2 = f(li[tree[now]], r);
		//算出两条线四个端点的y
		if (ly1 <= ly2 && ry1 <= ry2)return;
		//第二种情况
		if (ly1 >= ly2 && ry1 >= ry2) { tree[now] = k; return; }
		//第三种情况
		double in = inter(li[k], li[tree[now]]);
		//第四种情况
		if (ly1 >= ly2)
		{
			if (in <= mid)update(ls, l, mid, k, L, R);
			else update(rs, mid + 1, r, tree[now], L, R), tree[now] = k;
		}
		else
		{
			if (in > mid)update(rs, mid + 1, r, k, L, R);
			else update(ls, l, mid, tree[now], L, R), tree[now] = k;
		}
	}
	//没到要改的区间就继续递归 线段树
	if (L <= mid)update(ls, l, mid, k, L, R);
	if (mid < R)update(rs, mid + 1, r, k, L, R);
}

然后是查询操作，因为下面的模板题是要找出哪条直线的编号，所以我下面的例子是找到编号。
如果是想找大小的话，可以用下面这个先找出编号，在计算y值。也可以在上面的线段树多记一个mx数组来表示区间最大值（具体可以看第二个例题）

int maxn(int x,int a,int b)//计算编号
{
	return f(li[a],x)>f(li[b],x)?a:b;
}
int get(int now,int l,int r,int k)//要理解标记永久化的意思，不想普通线段树一样找到区间就返回，要递归到底。
{
	int res=0;
	if(tree[now])res=maxn(k,res,tree[now]);
	if(l==r)return res;//特别的
	int mid=(l+r)>>1;
	if(k<=mid)res=maxn(k,res,get(ls,l,mid,k));
	else res=maxn(k,res,get(rs,mid+1,r,k));
	return res;
}

例题

模板题

#include<bits/stdc++.h>
#define pll pair<int,int>
#define line pair<double,double>
#define mp make_pair
#define pb push_back
#define ll long long
#define INF 1e18
#define inf 0x3f3f3f3f
#define pi acos(-1)
#define db(x) cout<<x<<" "
#define dl(x) cout<<x<<endl
#define ls now<<1
#define rs now<<1|1
using namespace std;
const int mod = 1e9+7;
const int MAXN = 2e4 + 10;
const int N = 1e5 + 10;
const double eps =1e-6; 
int n, m;
int tot;
line li[N];
double f(line x,int X)
{
	return x.first*X+x.second; 
}
double inter(line x,line y)
{
	return (y.second-x.second)/(x.first-y.first); 
}
int tree[N<<2];

void add(int now,int l,int r,int k,int L,int R)
{
	int mid=(l+r)>>1;
	if(L<=l&&r<=R)
	{
		if(!tree[now])
		{
			tree[now]=k;
			return;
		}
		double ly1=f(li[k],l),ry1=f(li[k],r),ly2=f(li[tree[now]],l),ry2=f(li[tree[now]],r);
		if(ly1<=ly2&&ry1<=ry2)return;
		if(ly1>=ly2&&ry1>=ry2){tree[now]=k;return;}
		double in=inter(li[k],li[tree[now]]);
		if(ly1>=ly2)
		{
			if(in<=mid)add(ls,l,mid,k,L,R);
			else add(rs,mid+1,r,tree[now],L,R),tree[now]=k;
		}
		else
		{
			if(in>mid)add(rs,mid+1,r,k,L,R);
			else add(ls,l,mid,tree[now],L,R),tree[now]=k;
		}
	}
	if(L<=mid)add(ls,l,mid,k,L,R);
	if(mid<R)add(rs,mid+1,r,k,L,R); 
}
int maxn(int x,int a,int b)
{
	return f(li[a],x)>f(li[b],x)?a:b;
}
int get(int now,int l,int r,int k)
{
	int res=0;
	if(tree[now])res=maxn(k,res,tree[now]);
	if(l==r)return res;
	int mid=(l+r)>>1;
	if(k<=mid)res=maxn(k,res,get(ls,l,mid,k));
	else res=maxn(k,res,get(rs,mid+1,r,k));
	return res;
}
int ans;
int h(int k,int mod1)
{
	return (k+ans-1)%mod1+1;
}
void work()
{
 	cin>>n;
 	int M=39989;
 	for(int i=1;i<=n;i++)
 	{
 		int op;
		cin>>op;
		if(op)
		{
			int a,b,c,d;
			cin>>a>>b>>c>>d;
			a=h(a,M);c=h(c,M);b=h(b,1e9);d=h(d,1e9); 
			li[++tot]=(a==c?mp(.0,(double)max(b,d)):mp((d-b)*1.0/(c-a),(double)(b-(d-b)*1.0/(c-a)*a)));
			add(1,1,M,tot,min(a,c),max(a,c));
		}
		else
		{
			int k;cin>>k;
			k=h(k,M);
			ans=get(1,1,M,k);
			cout<<ans<<endl;
		}
	}
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int _ = 1;
	//cin >> _;
	while (_--)work();
	return 0;
}

树剖+李超线段树

#include<bits/stdc++.h>
#define pll pair<int,int>
#define line pair<double,double>
#define mp make_pair
#define pb push_back
#define ll long long
#define INF 123456789123456789
#define inf 0x3f3f3f3f
#define pi acos(-1)
#define db(x) cout<<x<<" "
#define dl(x) cout<<x<<endl
#define ls now<<1
#define rs now<<1|1
using namespace std;
const int mod = 1e9+7;
const int MAXN = 2e5 + 10;
const int N = 1e5 + 10;
const double eps =1e-6;
int n, m;
struct node {
	int t, nex;
	ll len;
}e[MAXN];
int head[N], cnt;
void add(int a, int b, ll c)
{
	e[++cnt].len = c; e[cnt].nex = head[a]; e[cnt].t = b; head[a] = cnt;
}

ll dep[N], dis[N], siz[N],hson[N],fa[N],dft;
ll rnk[N], dfn[N], top[N];
void dfs1(int u,int f)
{
	siz[u] = 1;
	hson[u] = -1;
	for (int i = head[u]; i; i = e[i].nex)
	{
		int v = e[i].t;
		if (v == f)continue;
		dis[v] = dis[u] + e[i].len;
		dep[v] = dep[u] + 1;
		fa[v] = u;
		dfs1(v, u);
		siz[u] += siz[v];
		if (hson[u] == -1 || siz[v] > siz[hson[u]])hson[u] = v;
	}
}
void dfs2(int u,int t)
{
	dfn[u] = ++dft; rnk[dft] = u; top[u] = t;
	if (hson[u] != -1)dfs2(hson[u], t);
	for (int i = head[u]; i; i = e[i].nex)
	{
		int v = e[i].t;
		if (v == hson[u] || v == fa[u])continue;
		dfs2(v, v);
	}
}
int lca(int u, int v)
{
	ll f1 = top[u], f2 = top[v];
	while (f1!=f2)
	{
		if (dep[f1] < dep[f2])swap(f1, f2), swap(u, v);
		u = fa[f1]; f1 = top[u];
	}
	return dep[u] < dep[v]?u:v;
}

ll K[N << 2], B[N << 2];
int tot;
struct tr
{
	int l, r;
	int tag;
	ll mn;
}tree[N<<2];
ll get(int p, int u)
{
	return K[p]*dis[rnk[u]] + B[p];
}
void build(int now, int l, int r)
{
	tree[now].mn = INF, tree[now].tag = 1;
	tree[now].l = l, tree[now].r = r;
	if (l == r)return;
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
}
void push_up(int now)
{
	tree[now].mn = min(tree[now].mn, min(tree[ls].mn, tree[rs].mn));
}
void update(int now, int l, int r, int p)
{
	int mid = (tree[now].l + tree[now].r) >> 1;
	int k = tree[now].tag;
	if (l <= tree[now].l && tree[now].r <= r)
	{
		ll ly1 = get(p, tree[now].l), ry1 = get(p, tree[now].r);
		ll ly2 = get(k, tree[now].l), ry2 = get(k, tree[now].r);
		if (ly1 >= ly2 && ry1 >= ry2)return;
		if (ly1 < ly2 && ry1 < ry2)
		{
			tree[now].tag = p;
			tree[now].mn = min(tree[now].mn, min(get(p, tree[now].l), get(p, tree[now].r)));
			return;
		}
		if (ly1 <= ly2)
		{
			if (get(p, mid) > get(k, mid))update(ls, l, r, p);
			else
			{
				update(rs, l, r, k);
				tree[now].tag = p;
			}
		}
		else
		{
			if (get(p, mid) > get(k, mid))update(rs, l, r, p);
			else
			{
				update(ls, l, r, k);
				tree[now].tag = p;
			}
		}
		tree[now].mn = min(tree[now].mn, min(get(tree[now].tag, tree[now].l), get(tree[now].tag, tree[now].r)));
		push_up(now);
		return;
	}
	if (l <= mid)update(ls, l, r, p);
	if (mid < r)update(rs,l, r, p);
	push_up(now);
}
ll query(int now, int l, int r)
{
	if (l <= tree[now].l && tree[now].r <= r)return tree[now].mn;
	ll ans = min(get(tree[now].tag, max(l, tree[now].l)), get(tree[now].tag, min(r, tree[now].r)));
	int mid = (tree[now].l + tree[now].r) >> 1;
	if (l <= mid)ans = min(ans, query(ls, l, r));
	if (mid < r)ans = min(ans, query(rs, l, r));
	return ans;
}
void op1(int u, int v, int k)
{
	int f1 = top[u], f2 = top[v];
	while (f1 != f2)
	{
		update(1, dfn[f1], dfn[u], k);
		u = fa[f1]; f1 = top[u];
	}
	update(1, dfn[v], dfn[u], k);
}
ll op2(int u, int v)
{
	int f1 = top[u], f2 = top[v];
	ll res = INF;
	while (f1 != f2)
	{
		if (dep[f1] < dep[f2])swap(f1, f2), swap(u, v);
		res=min(res,query(1, dfn[f1], dfn[u]));
		u = fa[f1]; f1 = top[u];
	}
	if (dep[u] < dep[v])swap(f1, f2), swap(u, v);
	res = min(res, query(1, dfn[v], dfn[u]));
	return res;
}
void work()
{
	cin >> n >> m;
	for (int i = 1; i < n; i++)
	{
		ll a, b, c;
		cin >> a >> b >> c;
		add(a, b, c); add(b, a, c);
	}

	dfs1(1,0);
	dfs2(1, 1);
	B[++tot] = INF; K[tot] = 0;
	build(1, 1, n);

	for (int i = 1; i <= m; i++)
	{
		int op;
		cin >> op;
		if (op == 1)
		{
			int s, t;
			ll a, b;
			cin >> s >> t >> a >> b;
			int lc = lca(s, t);//主要是这里两个K B的处理
			//cout << lc << endl;
			K[++tot] = -a; B[tot] = b + a * dis[s];
			op1(s, lc, tot);
			K[++tot] = a; B[tot] = b + a * dis[s] - a* 2 * dis[lc];
			op1(t, lc, tot);
		}
		else
		{
			int l, r;
			cin >> l >> r;
			cout << op2(l, r) << endl;
		}
	}
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int _ = 1;
	//cin >> _;
	while (_--)work();
	return 0;
}