树套树-线段树套平衡树

作用

线段树的作用是区间修改和查询，平衡树的作用是查询第k大，k的排名，前驱，后继。这两个结合起来，就变成了可以区间修改和查询第k大，k的排名，前驱，后继的数据结构：树套树-线段树套平衡树。

实现

先构造出线段树，每个线段树除了记录左边界和右边界之外，还储存了一棵平衡树（当然实际上只需要储存根节点），对应着这一个区间的所有数。每次修改区间L~R时，需要将所有包含L~R的线段树节点的平衡树都修正。操作其实没有什么难点，和普通线段树一样分块处理即可，效率为 O(log22(n)) 。

但是查询区间第k大不能像普通线段树一样，必须用二分枚举答案mid，然后查询mid的排名，如果排名<=k就增大mid，否则减小mid。假设二分跨度为t，则效率为 O(log22(n)∗log2(t)) 。

ps：树套树常数较大，请谨慎使用。

模板

以BZOJ3196为例，这里使用的是线段树套Treap。注意细节处理。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=,maxt=,MAXINT=((<<)-)*+;

int n,te,a[maxn+];
//============================================================
struct Node
{
    Node *son[];
    int val,fix,si,w;
    int cmp(int k) {if (k==val) return -;if (k<val) return ; else return ;}
    void Pushup() {si=son[]->si+w+son[]->si;}
};
typedef Node* P_node;
Node tem[maxt+];
P_node null=tem,len=null;
P_node newNode(int k)
{
    len++;len->son[]=len->son[]=null;
    len->si=len->w=;len->val=k;len->fix=rand();
    return len;
}
void Rotate(P_node &p,int d)
{
    P_node t=p->son[d^];p->son[d^]=t->son[d];t->son[d]=p;
    p->Pushup();t->Pushup();p=t;
}
void Insert(P_node &p,int k)
{
    if (p==null) {p=newNode(k);return;}
    int d=p->cmp(k);
    if (d==-) p->w++; else
    {
        Insert(p->son[d],k);
        if (p->son[d]->fix>p->fix) Rotate(p,d^);
    }
    p->Pushup();
}
void Delete(P_node &p,int k)
{
    if (p==null) return;
    int d=p->cmp(k);
    if (d==-)
    {
        if (p->w>) p->w--; else
        if (p->son[]==null) p=p->son[]; else
        if (p->son[]==null) p=p->son[]; else
        {
            int d;if (p->son[]->fix>p->son[]->fix) d=; else d=;
            Rotate(p,d);if (p==null) return;Delete(p->son[d],k);
        }
        if (p==null) return;
    } else Delete(p->son[d],k);
    p->Pushup();
}
int getrank(P_node p,int k) //对于不存在的k，排名是k后继的排名
{
    if (p==null) return ;
    int d=p->cmp(k);
    if (d==-) return p->son[]->si+; else
    if (d==) return getrank(p->son[],k); else
    return getrank(p->son[],k)+p->son[]->si+p->w;
}
int getpre(P_node p,int k)
{
    if (p==null) return -MAXINT;
    int d=p->cmp(k);
    if (d==) return max(getpre(p->son[],k),p->val); else
    return getpre(p->son[],k);
}
int getsuf(P_node p,int k)
{
    if (p==null) return MAXINT;
    int d=p->cmp(k);
    if (d==) return min(getsuf(p->son[],k),p->val); else
    return getsuf(p->son[],k);
} //以上为Treap
//============================================================
struct SegmentTree
{
    int l[*maxn+],r[*maxn+];P_node ro[*maxn+]; //只保留根指针
    void Build(int p,int L,int R)
    {
        l[p]=L;r[p]=R;ro[p]=null;
        if (L==R) return;
        int mid=L+(R-L>>);
        Build(p<<,L,mid);Build(p<<|,mid+,R);
    }
    void Seg_Insert(int p,int L,int k)
    {
        if (L<l[p]||r[p]<L) return;
        if (l[p]<=L&&L<=r[p]) Insert(ro[p],k);
        //这里不是L<=l[p]&&r[p]<=L，因为所有包含L的节点都要插入k
        if (l[p]==r[p]) return;
        Seg_Insert(p<<,L,k);Seg_Insert(p<<|,L,k);
    }
    void Seg_Delete(int p,int L,int k)
    {
        if (L<l[p]||r[p]<L) return;
        if (l[p]<=L&&L<=r[p]) Delete(ro[p],k);
        //同理
        if (l[p]==r[p]) return;
        Seg_Delete(p<<,L,k);Seg_Delete(p<<|,L,k);
    }
    int Seg_rank(int p,int L,int R,int k) //这个函数返回真正的答案-1，防止重复
    {
        if (R<l[p]||r[p]<L) return ;
        if (L<=l[p]&&r[p]<=R) return getrank(ro[p],k)-;
        //这里是普通线段树查询，所以是L<=l[p]&&r[p]<=R
        return Seg_rank(p<<,L,R,k)+Seg_rank(p<<|,L,R,k);
    }
    int Seg_kth(int l,int r,int k)
    {
        int L=,R=;
        while (L<=R) //二分
        {
            int mid=L+(R-L>>),rk=Seg_rank(,l,r,mid)+;
            if (rk<=k) L=mid+; else R=mid-;
        }
        return R;
    }
    int Seg_pre(int p,int L,int R,int k)
    {
        if (R<l[p]||r[p]<L) return -MAXINT;
        if (L<=l[p]&&r[p]<=R) return getpre(ro[p],k);
        return max(Seg_pre(p<<,L,R,k),Seg_pre(p<<|,L,R,k));
    }
    int Seg_suf(int p,int L,int R,int k)
    {
        if (R<l[p]||r[p]<L) return MAXINT;
        if (L<=l[p]&&r[p]<=R) return getsuf(ro[p],k);
        return min(Seg_suf(p<<,L,R,k),Seg_suf(p<<|,L,R,k));
    }
};
SegmentTree tr; //以上为线段树
//============================================================
bool Eoln(char ch) {return ch==||ch==||ch==EOF;}
int readi(int &x)
{
    int tot=,f=;char ch=getchar(),lst=' ';
    while ('9'<ch||ch<'0') {if (ch==EOF) return EOF;lst=ch;ch=getchar();}
    if (lst=='-') f=-f;
    while ('0'<=ch&&ch<='9') tot=tot*+ch-,ch=getchar();
    x=tot*f;
    return Eoln(ch);
}
void LNR(P_node ro)
{
    if (ro==null) return;
    LNR(ro->son[]);for (int i=;i<=ro->w;i++) printf("%d\n",ro->val);LNR(ro->son[]);
}
int main()
{
    freopen("STBST.in","r",stdin);
    freopen("STBST.out","w",stdout);
    readi(n);readi(te);tr.Build(,,n);
    for (int i=;i<=n;i++) readi(a[i]),tr.Seg_Insert(,i,a[i]);
    while (te--)
    {
        int td,x,y,z;readi(td);readi(x);readi(y);
        switch (td)
        {
            case :readi(z);printf("%d\n",tr.Seg_rank(,x,y,z)+);break;
            case :readi(z);printf("%d\n",tr.Seg_kth(x,y,z));break;
            case :tr.Seg_Delete(,x,a[x]);tr.Seg_Insert(,x,y);a[x]=y;break;
            case :readi(z);printf("%d\n",tr.Seg_pre(,x,y,z));break;
            case :readi(z);printf("%d\n",tr.Seg_suf(,x,y,z));break;
        }
    }
    return ;
}