李超线段树简易讲解

本文主要是介绍李超线段树简易讲解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

大佬的博客讲的很清晰
李超线段树就是标记永久化维护区间线段最值的数据结构
假设有下列的问题：
给定平面中\(n\)条线段，(给出斜率\(k\)和截距\(b\)，并且知道线段左右端点的横坐标值为多少)，然后\(m\)个询问，每次给定\(x = x_0\)，问和\(x = x_0\)相交的直线中，横坐标值最大为多少。
很明显\(n\)和\(m\)数据范围大了之后，我们无法暴力，此时看到区间端点，可以想能否用数据结构维护这个东西，即----李超线段树。

复杂度分析：
每次查询是\(logn\)的，
每次插入更新，我们可以把整个权值的域划分为\(logn\)个区间，这里是同一般更新的，但是每个区间内，我们要下放非优势线段，所以又套了一个\(log\)，总体更新复杂度为\(log^2n\)，但貌似常数比较小。

维护这个线段可以用结构体和数组实现，我个人偏好结构体一些，比较好写。
这里用结构体里面带\(flag\)来判断是否被标记过了，因为更新牵扯到优势线段的更新，不好操作，另开一个数组来维护

bool flag[N];
struct seg {
	double k,b;
	int l,r;
	seg(){}
	seg(double _k,double _b,int _l,int _r) {
		k = _k,b = _b,l = _l,r = _r;
	}
	double gety(const int &pos) const {//返回某处的函数值
		return k * pos + b;
	}
	double crossx(const seg &ts) const {//获得两个线段之间的交点
		return (ts.b - b) / (k - ts.k);
	}
}tree[N << 2];

更新过程主要是其实就是涉及到\(mid\)和端点处\(l,r\)几处的函数值讨论一下，即可完成，画图会更清晰的理解。

void modify(int rt,int l,int r,seg ins) {
	int mid = (l + r) >> 1;
	if(l >= ins.l && r <= ins.r) {
		if(!flag[rt]) {//未被覆盖 直接更新
			tree[rt] = ins; flag[rt] = true; return ;
		}
		if(ins.gety(l) - tree[rt].gety(l) > eps && ins.gety(r) - tree[rt].gety(r) > eps) {//当前插入的线段整体更优
			tree[rt] = ins; return ;
		}
		if(ins.gety(l) - tree[rt].gety(l) > eps || ins.gety(r) - tree[rt].gety(r) > eps) {//任有一段大
			if(ins.gety(mid) - tree[rt].gety(mid) > eps) swap(ins,tree[rt]);//tree保持的是当前最优线段
			//画画图就理解了
			if(ins.crossx(tree[rt]) - mid < -eps) modify(lson,l,mid,ins);
			else modify(rson,mid+1,r,ins);
		}
		return ;
	}
	if(ins.l <= mid) modify(lson,l,mid,ins);
	if(ins.r > mid) modify(rson,mid+1,r,ins);
}

查询就比较普通

double query(int rt,int l,int r,int pos) {
	if(l == r) return tree[rt].gety(pos);
	int mid = (l + r) >> 1;
	double ans = tree[rt].gety(pos);
	if(pos <= mid) ans = max(ans,query(lson,l,mid,pos));
	else ans = max(ans,query(rson,mid+1,r,pos));
	return ans;
}

到此就是大致的粗糙简易模板了

\(1.\)BZOJ 1568 裸的模板题

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-10;
const int ma = 50000;
const int N = 1e5 + 10;
int n;
char op[10];
struct seg {
	double k,b;
	int l,r,fg;
	double gety(const int &pos) const {
		return k * pos + b;
	}
	double crossx(const seg &a) const {
		return (a.b - b) / (k - a.k);
	}
}tree[N<<2];
void build(int rt,int l,int r) {
	tree[rt].k = 0,tree[rt].b = 0,tree[rt].l = 1,tree[rt].r = ma;
	if(l == r) return ;
	int mid = (l + r) >> 1;
	build(lson,l,mid); build(rson,mid+1,r);
}
void modify(int rt,int L,int R,seg k) {
	if(L >= k.l && R <= k.r) {
		// cout << rt << ' ' << tree[rt].fg << "****\n";
		if(k.gety(L) - tree[rt].gety(L) > eps && k.gety(R) - tree[rt].gety(R) > eps) {
			tree[rt] = k; return ;
		}
		if(k.gety(L) - tree[rt].gety(L) > eps || k.gety(R) - tree[rt].gety(R) > eps) {
			int mid = (L + R) >> 1;
			if(k.gety(mid) - tree[rt].gety(mid) > eps) swap(k,tree[rt]);//tree[rt] 存最优
			if(k.crossx(tree[rt]) - mid < -eps) modify(lson,L,mid,k);
			else modify(rson,mid+1,R,k);
		}
		return ;
	}
	int mid = (L + R) >> 1;
	if(k.l <= mid) modify(lson,L,mid,k);
	if(k.r > mid) modify(rson,mid+1,R,k);
}
double query(int rt,int l,int r,int pos) {
	if(l == r) return tree[rt].gety(pos);
	int mid = (l + r) >> 1;
	double ans = tree[rt].gety(pos);
	if(pos <= mid) return max(ans,query(lson,l,mid,pos));
	else return max(ans,query(rson,mid+1,r,pos));
}

int main() {
	scanf("%d",&n);
	build(1,1,ma);
	for(int i = 1;i <= n;i ++) {
		scanf("%s",&op);
		if(op[0] == 'P') {
			double k,b;
			scanf("%lf%lf",&b,&k);
			seg tmp;
			tmp.k = k,tmp.b = b - k,tmp.l = 1,tmp.r = ma;
			modify(1,1,ma,tmp);
		}
		else if(op[0] == 'Q') {
			int x;
			scanf("%d",&x);
			// cout << query(1,1,ma,x) << '\n';
			int res = (int)(query(1,1,ma,x) / 100);
			printf("%d\n",res);
		}
	}
	return 0;
}
/*
100
Project 5.10200 0.65000
Project 2.76200 1.43000
Query 4
Query 2
Project 3.80200 1.17000
Query 2
Query 3
Query 1
Project 4.58200 0.91000
Project 5.36200 0.39000
*/

\(2.\)BZOJ3938 转换一下题意建立李超树模型

思路：对于每个机器人他距离原点的位置\(x\)其实是和时间\(t\)相关联的，也就是说每个机器人的位置其实就是\(x - t\)的一次函数图像，对应每个机器人的每段\(x - t\)图像都可变为一个线段，而又因为题目求得距离原点的距离最大值，所以我们就建两棵树分别维护整个区间上的最大值和最小值，最后取绝对值大者皆可。
时间范围大，离散化一下，存一下线段，基本变成了模板题。

这道题细节还是有的，注意别忘了存下来最开始的位置也当做线段，每个机器人最后一次操作和时间范围边界点也当做线段，两边都不要遗漏。
因为插入的时候，交点和\(mid\)大小符号判断写反了，debug了一天，都快wa吐了......

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 1e5 + 10;
const int M = 6e5 + 10;
bool flag[2][M<<2];
struct seg {
	ll k,b;
	int l,r;
	seg(){}
	seg(ll _k,ll _b,int _l,int _r) {
		k = _k,b = _b,l = _l,r = _r;
	}
	ll gety(const ll &pos) const {
		return k * pos + b;
	}
	ll crossx(const seg &ts) const {
		return (ts.b - b) / (k - ts.k); 
	}
}tree[2][M << 2];
int n,m;
ll init[N],lsh[M];
int cnt;
struct Q {
	ll v,ti;
	int id;
	char op[10];
}q[M];
void modifymax(int rt,int l,int r,seg ins) {
	int mid = (l + r) >> 1;
	if(l >= ins.l && r <= ins.r) {
		if(!flag[0][rt]) {
			tree[0][rt] = ins; flag[0][rt] = true; return ;
		}
		if(ins.gety(lsh[l]) > tree[0][rt].gety(lsh[l]) && ins.gety(lsh[r]) > tree[0][rt].gety(lsh[r])) {
			tree[0][rt] = ins; return ;
		}
		if(ins.gety(lsh[l]) > tree[0][rt].gety(lsh[l]) || ins.gety(lsh[r]) > tree[0][rt].gety(lsh[r])) {
			if(ins.gety(lsh[mid]) > tree[0][rt].gety(lsh[mid])) swap(ins,tree[0][rt]);
			if(ins.crossx(tree[0][rt]) < lsh[mid]) modifymax(lson,l,mid,ins);
			else modifymax(rson,mid+1,r,ins);
		}
		return ;
	}
	if(ins.l <= mid) modifymax(lson,l,mid,ins);
	if(ins.r > mid) modifymax(rson,mid+1,r,ins);
}
void modifymin(int rt,int l,int r,seg ins) {
	int mid = (l + r) >> 1;
	if(l >= ins.l && r <= ins.r) {
		if(!flag[1][rt]) {
			tree[1][rt] = ins; flag[1][rt] = true; return ;
		}
		if(ins.gety(lsh[l]) < tree[1][rt].gety(lsh[l]) && ins.gety(lsh[r]) < tree[1][rt].gety(lsh[r])) {
			tree[1][rt] = ins; return ;
		}
		if(ins.gety(lsh[l]) < tree[1][rt].gety(lsh[l]) || ins.gety(lsh[r]) < tree[1][rt].gety(lsh[r])) {
			if(ins.gety(lsh[mid]) < tree[1][rt].gety(lsh[mid])) swap(ins,tree[1][rt]);
			if(ins.crossx(tree[1][rt]) < lsh[mid]) modifymin(lson,l,mid,ins);
			else modifymin(rson,mid+1,r,ins);
		}
		return ;
	}
	if(ins.l <= mid) modifymin(lson,l,mid,ins);
	if(ins.r > mid) modifymin(rson,mid+1,r,ins);
}
ll res1,res2;
ll qmax(int rt,int l,int r,int pos) {
	// if(flag[0][rt]) res1 = max(res1,tree[0][rt].gety(lsh[pos]));
	if(l == r) return tree[0][rt].gety(lsh[pos]);
	int mid = (l + r) >> 1;
	ll ans = tree[0][rt].gety(lsh[pos]);
	if(pos <= mid) ans = max(ans,qmax(lson,l,mid,pos));
	else ans = max(ans,qmax(rson,mid+1,r,pos));
	return ans;
}

ll qmin(int rt,int l,int r,int pos) {
	// if(flag[1][rt]) res2 = min(res2,tree[1][rt].gety(lsh[pos]));
	if(l == r) return tree[1][rt].gety(lsh[pos]);
	int mid = (l + r) >> 1;
	ll ans = tree[1][rt].gety(lsh[pos]);
	if(pos <= mid) return min(ans,qmin(lson,l,mid,pos));
	else return min(ans,qmin(rson,mid+1,r,pos));
}

bool vis[N];
ll lastk[N],lastb[N],lastt[N];
int getid(ll x) {
	return lower_bound(lsh + 1,lsh + 1 + cnt,x) - lsh;
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i ++) {
		scanf("%lld",&lastb[i]);
	}
	for(int i = 1;i <= m;i ++) {
		scanf("%lld%s",&q[i].ti,q[i].op);
		lsh[++cnt] = q[i].ti; 
		if(q[i].op[0] == 'c') {
			scanf("%d%lld",&q[i].id,&q[i].v);
		}
	}
	lsh[++cnt] = 0;//用于插入初始值
	sort(lsh + 1,lsh + 1 + cnt);
	cnt = unique(lsh + 1,lsh + 1 + cnt) - lsh - 1;
	for(int i = 1;i <= m;i ++) {
		if(q[i].op[0] == 'c') {
			int no = q[i].id;
			// vis[no] = 1;
			int l = getid(lastt[no]),r = getid(q[i].ti);
			// cout << lastk[no] << ' ' << lastb[no] << ' ' << l << ' ' << r << "***\n";
			modifymax(1,1,cnt,seg(lastk[no],lastb[no],l,r));
			modifymin(1,1,cnt,seg(lastk[no],lastb[no],l,r));
			lastb[no] = lastb[no] + q[i].ti * (lastk[no] - q[i].v);
			lastk[no] = q[i].v;lastt[no] = q[i].ti;
		}
	}
	for(int i = 1;i <= n;i ++) {
		int l = getid(lastt[i]);
		modifymax(1,1,cnt,seg(lastk[i],lastb[i],l,cnt));
		modifymin(1,1,cnt,seg(lastk[i],lastb[i],l,cnt));
	}
	for(int i = 1;i <= m;i ++) {
		if(q[i].op[0] == 'q') {
			int no = q[i].id;
			int time = getid(q[i].ti);
			res1 = res2 = 0;
			res1 = qmax(1,1,cnt,time); res2 = qmin(1,1,cnt,time);
			// ll res1 = qmax(1,1,cnt,time); ll res2 = qmin(1,1,cnt,time);
			// cout << res1 << ' ' << res2 << '\n';
			ll res = max(res1,-res2);
			printf("%lld\n",res);
		}
	}
	return 0;
}
/*
4 5
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query
*/

数组标记线段实现：

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 1e5 + 10;
const int M = 6e5 + 10;
bool flag[2][M<<2];
ll tagk[2][M<<2],tagb[2][M<<2];
int n,m;
ll init[N],lsh[M];
int cnt;
struct Q {
	ll v,ti;
	int id;
	char op[10];
}q[M];
ll cal(ll k,ll b,ll x) {
	return k * x + b;
}
void modifymax(int rt,int l,int r,int L,int R,ll k,ll b) {
	int mid = (l + r) >> 1;
	if(l >= L && r <= R) {
		if(!flag[0][rt]) {
			tagk[0][rt] = k,tagb[0][rt] = b,flag[0][rt] = true; return ;
		}
		// if(cal(k,b,lsh[l]) > cal(tagk[0][rt],tagb[0][rt],lsh[l]) && cal(k,b,lsh[r]) > cal(tagk[0][rt],tagb[0][rt],lsh[r])) {
		ll f1 = k * lsh[l] + b,f2 = tagk[0][rt] * lsh[l] + tagb[0][rt];
		ll f3 = k * lsh[r] + b,f4 = tagk[0][rt] * lsh[r] + tagb[0][rt];
		if(f1 <= f2 && f3 <= f4) return ;
		if(f1 >= f2 && f3 >= f4) {
			tagk[0][rt] = k,tagb[0][rt] = b; return ;
		}
		ll crossx = (tagb[0][rt] - b) / (k - tagk[0][rt]);
		if(f1 >= f2) {
			if(crossx <= lsh[mid]) modifymax(lson,l,mid,L,R,k,b);
			else { modifymax(rson,mid+1,r,L,R,tagk[0][rt],tagb[0][rt]); tagk[0][rt] = k,tagb[0][rt] = b; }
		}
		else {
			if(crossx > lsh[mid]) modifymax(rson,mid+1,r,L,R,k,b);
			else { modifymax(lson,l,mid,L,R,tagk[0][rt],tagb[0][rt]); tagk[0][rt] = k,tagb[0][rt] = b; }		
		}
		return ;
	}
	if(L <= mid) modifymax(lson,l,mid,L,R,k,b);
	if(R > mid) modifymax(rson,mid+1,r,L,R,k,b);
}
void modifymin(int rt,int l,int r,int L,int R,ll k,ll b) {
	int mid = (l + r) >> 1;
	if(l >= L && r <= R) {
		if(!flag[1][rt]) {
			tagk[1][rt] = k,tagb[1][rt] = b,flag[1][rt] = true; return ; 
		}
		ll f1 = k * lsh[l] + b,f2 = tagk[1][rt] * lsh[l] + tagb[1][rt];
		ll f3 = k * lsh[r] + b,f4 = tagk[1][rt] * lsh[r] + tagb[1][rt];
		if(f1 >= f2 && f3 >= f4) return ;
		if(f1 <= f2 && f3 <= f4) {
			tagk[1][rt] = k,tagb[1][rt] = b; return ;
		}
		ll crossx = (tagb[1][rt] - b) / (k - tagk[1][rt]);
		if(f1 <= f2) {
			if(crossx <= lsh[mid]) modifymin(lson,l,mid,L,R,k,b);
			else { modifymin(rson,mid+1,r,L,R,tagk[1][rt],tagb[1][rt]); tagk[1][rt] = k,tagb[1][rt] = b; }
		}
		else {
			if(crossx > lsh[mid]) modifymin(rson,mid+1,r,L,R,k,b);
			else { modifymin(lson,l,mid,L,R,tagk[1][rt],tagb[1][rt]); tagk[1][rt] = k,tagb[1][rt] = b; }		
		}
		return ;
	}
	if(L <= mid) modifymin(lson,l,mid,L,R,k,b);
	if(R > mid) modifymin(rson,mid+1,r,L,R,k,b);
}
ll res1,res2;
void qmax(int rt,int l,int r,int pos) {
	if(flag[0][rt]) res1 = max(res1,tagk[0][rt] * lsh[pos] + tagb[0][rt]);
	if(l == r) return ;//cal(tagk[0][rt],tagb[0][rt],lsh[pos]);
	int mid = (l + r) >> 1;
	if(pos <= mid) qmax(lson,l,mid,pos);
	else qmax(rson,mid+1,r,pos);
}
void qmin(int rt,int l,int r,int pos) {
	if(flag[1][rt]) res2 = min(res2,tagk[1][rt] * lsh[pos] + tagb[1][rt]);
	if(l == r) return ;
	int mid = (l + r) >> 1;
	if(pos <= mid) qmin(lson,l,mid,pos);
	else qmin(rson,mid+1,r,pos);
}
bool vis[N];
ll lastk[N],lastb[N],lastt[N];
int getid(ll x) {
	return lower_bound(lsh + 1,lsh + 1 + cnt,x) - lsh;
}

int main() {
	scanf("%d%d",&n,&m);
	ll ma = 0;
	for(int i = 1;i <= n;i ++) {
		scanf("%lld",&lastb[i]);
		ma = max(ma,lastb[i]);
	}
	for(int i = 1;i <= m;i ++) {
		scanf("%lld%s",&q[i].ti,q[i].op);
		lsh[++cnt] = q[i].ti; 
		if(q[i].op[0] == 'c') {
			scanf("%d%lld",&q[i].id,&q[i].v);
		}
	}
	lsh[++cnt] = 0;//用于插入初始值
	sort(lsh + 1,lsh + 1 + cnt);
	cnt = unique(lsh + 1,lsh + 1 + cnt) - lsh - 1;
	for(int i = 1;i <= m;i ++) {
		if(q[i].op[0] == 'c') {
			int no = q[i].id;
			int l = getid(lastt[no]),r = getid(q[i].ti);
			// cout << lastk[no] << ' ' << lastb[no] << ' ' << l << ' ' << r << "***\n";
			modifymax(1,1,cnt,l,r,lastk[no],lastb[no]);
			modifymin(1,1,cnt,l,r,lastk[no],lastb[no]);
			lastb[no] = lastb[no] + q[i].ti * (lastk[no] - q[i].v);
			lastk[no] = q[i].v;lastt[no] = q[i].ti;
		}
	}
	for(int i = 1;i <= n;i ++) {
		int l = getid(lastt[i]);
		// cout << lastk[i] << ' ' << lastb[i] << ' ' << l << ' ' << cnt << "***\n";
		modifymax(1,1,cnt,l,cnt,lastk[i],lastb[i]);
		modifymin(1,1,cnt,l,cnt,lastk[i],lastb[i]);
	}
	for(int i = 1;i <= m;i ++) {
		if(q[i].op[0] == 'q') {
			int no = q[i].id;
			int time = getid(q[i].ti);
			res1 = res2 = 0;
			qmax(1,1,cnt,time);qmin(1,1,cnt,time);
			// ll res1 = qmax(1,1,cnt,time); ll res2 = qmin(1,1,cnt,time);
			ll res = max(res1,-res2);
			printf("%lld\n",res);
		}
	}
	return 0;
}
/*
4 5
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query
*/

这篇关于李超线段树简易讲解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

李超线段树简易讲解

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯