【算法学习/数据结构】李超树

简介

·李超树的具体实现过程：

我们先将每一条线段都表示成点斜式，接下来用\(k\)表示斜率，\(b\)截距。当我们插入一条线段\(y=kx+b\)的到区间\([l,r]\)（插入直线则是\([?inf,inf]\)）时候，我们需要判断这条线段是否可以更新这个这个区间的答案。我们记一条线段\(s\)为优势线段，表示在这个区间\([l,r]\)中的线段中，\(s\)在\(mid=(l+r)>>1\)这个点上的\(y\)的值是最大的。那么插入一条线段的时候，就会出现下面几种情况：

1. 当这个区间还没有优势线段的时候，就可以直接将该线段设成该区间的优势线段，然后返回。
2. 当这个区间已经有优势线段，如果插入线段在区间\([l,r]\)的值都比该优势线段大，那么就可以直接替换掉这个优势线段，然后返回。或者是在区间\([l,r]\)的都比该优势线段小，那么就可以直接返回了。
3. 当这个区间的优势线段\(seg\)和插入线段\(s\)存在某个交点的时候，显然，我们需要更新这个区间的子区间的优势线段的答案。我们假设交点位置为\(pos\)，该区间中点位置为\(mid\)，\(ysegl\),\(ysegr\)表示\(seg\)线段左右两个端点的y值，\([ysl,ysr]\)同理。如果\(ysegl<ysl\),\(ysegr>ysr\)，那么说明在\(pos\)右边为\(seg\)优，\(pos\)左边为\(s\)优，然后判断此时\(pos\)的位置，如果此时\(pos\)的位置在\(mid\)的左边，说明s这条优势线段仍然需要下方到子区间去，然后继续递归下去即可，另一半也是类似的。最后不要忘记更改本区间的优势线段就行了。

查询的话就比较简单了，像普通的线段树一样，如果当前区间在查询区间当中的话，那么就直接返回当前优势线段，否则递归处理，然后顺便和当前区间优势线段的\(y_{seg_{pos}}\)比较一下，返回值更加大的线段就行了。

·复杂度：对于查询每一个点的极值，复杂度都为\(O(log(n))\)。但是插入线段时，因为寻找插入的区间和标记都需要\(O(log(n))\)的时间，所以复杂度会是\(O(log^2(n))\)，最后的总复杂度是\(O(nlog^2(n))\)

板子

#include<bits/stdc++.h>
using namespace std;
char s[10];
int n,tr[200010],cnt=0;
double k[100010],b[100010];
double f(int now,int x){return k[now]*(x-1)+b[now];}
void update(int now,int l,int r,int x){
    if(f(x,l)>f(tr[now],l)&&f(x,r)>f(tr[now],r)){
	   tr[now]=x;
	   return ; 
	}
    if(f(x,l)<=f(tr[now],l)&&f(x,r)<=f(tr[now],r))return ;
    int mid=(l+r)/2;
    if(k[tr[now]]<k[x]){
        if(f(x,mid)>f(tr[now],mid)){
		   update(now<<1,l,mid,tr[now]);
		   tr[now]=x; 
	    }
        else update(now<<1|1,mid+1,r,x);
    }
    else{
        if(f(x,mid)>f(tr[now],mid)){
		   update(now<<1|1,mid+1,r,tr[now]);
		   tr[now]=x;
	    }
        else update(now<<1,l,mid,x);
    }
}
double query(int now,int l,int r,int x){
    if(l==r)return f(tr[now],x);
    int mid=(l+r)/2;
    if(x<=mid)return max(f(tr[now],x),query(now<<1,l,mid,x));
    else return max(f(tr[now],x),query(now<<1|1,mid+1,r,x));
}
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%s",s);
        if(s[0]==‘P‘){
            cnt++;
            scanf("%lf%lf",&b[cnt],&k[cnt]);
            update(1,1,50000,cnt);
        }
        else{
        	int x;
            scanf("%d",&x);
            printf("%.3lf\n",query(1,1,50000,x)) ;
        }
    }
    return 0;
}

写完好晚了……先这样吧

【算法学习/数据结构】李超树

原文：https://www.cnblogs.com/linskyQWQ/p/14257186.html