数据结构：树套树-替罪羊树套权值线段树

BZOJ3065

本题是在BZOJ上的处女A，实在不应该拿这样一道题来开头

平衡树套线段树应该是树套树问题里比较难的一种了，当然我记得还有一个替罪羊树套Trie树的题，我是不信自己能写出来的。

外层的平衡树来实现区间值得插入和修改，其实如果外层的插入是只在中间插入的话，可以不用平衡树的

为了避免旋转对内层数据结构的影响，这里的外层平衡树是不能够旋转的，像这种外层平衡树的题，外层的树一般都是替罪羊树，像无旋Treap一般是用来实现可持久化平衡树的

总的来说，各种树有各种树的用途，我如果只是一道单纯的平衡树的题，就根本没有必要用裸的替罪羊树维护了是不是

下面我来完整地解析一下实现过程：

const int maxn=70005;
const float alpha=0.75;
int n,m,root,gtmp,sz,lastans;
int v[maxn],dfn[maxn],rt[maxn],lch[maxn],rch[maxn];
//rt是替罪羊节点存的每一个线段树的根节点 
struct seg{int l,r,sum;}a[10000005];
vector<int> rec,t,p;

先来看声明部分，alpha是替罪羊平衡因子，记住如果是常数一定不要用int，会崩的

区间长度为n，m个询问，替罪羊树的根节点咱们叫root，gtmp是和重构子树有关的临时变量，sz是线段树节点个数，lastans是跟题目有关的一个变量

这里的替罪羊树是SOA，v是节点的值，dfn是节点的ID用来节省空间，rt是每一个替罪羊节点对应的权值线段树的根节点，lch和rch是替罪羊左右子树的ID

权值线段树是AOS，l存左子树ID，r存右子树ID，sum在这里就是子树的节点个数了，因为有这个sum在替罪羊树中的size就不必了

这里的权值线段树虽然是完全二叉树但是存的时候是存成数组链的，不支持完全二叉树的2n,2n+1的操作，其实主要原因是空间不够

rec用来存回收来的线段树节点，为了省空间，t是用来存替罪羊子树（或者说一个区间）所有的权值线段树节点，p用来存这个区间每一个节点的值

t和p是在查询的时候二分查询权值线段树的时候用的，因为这个线段树是用链存的，所以查询部分还是不太会，只是大概理解了个思路

void build(int &k,int l,int r)
{
    //cout<<"###5"<<endl;
    if(l>r) return;
    if(l==r)
    {
        k=dfn[l];
        insert(rt[k],0,70000,v[k],1);  //在替罪羊树的叶子节点插入权值线段树 
        return;
    }
    int mid=(l+r)>>1;k=dfn[mid];
    build(lch[k],l,mid-1);build(rch[k],mid+1,r);
    for(int i=l;i<=r;i++) insert(rt[k],0,70000,v[dfn[i]],1); 
}

这是建树操作，建替罪羊树，在建的过程中每一个节点都插入了一个权值线段树，这个线段树是一个一个插出来的，其中insert的最后一个参数就是所谓的权值

然后我们立刻看一下权值线段树怎么建的

void insert(int &k,int l,int r,int val,int f)  //每一个替罪羊节点插入权值线段树 
{
    //cout<<"###4"<<endl;
    if(k==0) k=newnode();
    if(l==r) {a[k].sum+=f;return;}
    int mid=(l+r)>>1;
    if(val<=mid) insert(a[k].l,l,mid,val,f);
    else insert(a[k].r,mid+1,r,val,f);
    a[k].sum=a[a[k].l].sum+a[a[k].r].sum;
    if(a[k].sum==0) reclaim(k); 
}

可以很明显看出来是线段树递归建树了，如果插完之后发现没有权值，直接回收

inline int newnode()
{
    //cout<<"###2"<<endl;
    if(rec.size()==0) return ++sz;
    else
    {
        int tmp=rec.back();
        rec.pop_back();
        return tmp;
    }
}

向（回收站）申请一个线段树节点空间

看一下怎么拆掉没用的线段树的

void reclaim(int &k)  //回收叶子的线段树空间
{
    //cout<<"###3"<<endl;
    if(k==0) return;
    rec.push_back(k);
    reclaim(a[k].l),reclaim(a[k].r);
    a[k].sum=0;k=0; 
}

查询就比较恶心了

void query(int k,int l,int r)  //提取出要查询的权值线段树?
{
    //cout<<"###8"<<endl;
    int L=a[rt[lch[k]]].sum,R=a[rt[k]].sum;
    if(l==1&&r==R) {t.push_back(rt[k]);return;}  //要查询的区间映射到了权值线段树 
    if(l<=L+1&&r>=L+1) p.push_back(v[k]);  //当前根节点在要查询的区间里 
    if(r<=L) query(lch[k],l,r);
    else if(l>L+1) query(rch[k],l-L-1,r-L-1);
    else
    {
        if(l<=L) query(lch[k],l,L);
        if(R>L+1) query(rch[k],1,r-L-1);
    }
}
int solve_query(int L,int R,int K) //二分权值线段树查询区间第k大 ?
{
    //cout<<"###9"<<endl;
    query(root,L,R);K--;
    int l=0,r=70000,s1=t.size(),s2=p.size();
    while(l<r)
    {
        int mid=(l+r)>>1,sum=0;
        for(int i=0;i<s1;i++) sum+=a[a[t[i]].l].sum;
        for(int i=0;i<s2;i++)
            if(p[i]>=l&&p[i]<=mid) sum++;
        if(K<sum)
        {
            for(int i=0;i<s1;i++) t[i]=a[t[i]].l;
            r=mid;
        }
        else
        {
            for(int i=0;i<s1;i++) t[i]=a[t[i]].r;
            l=mid+1;K-=sum;
        }
    } 
    t.clear(),p.clear();
    return l;
}

上面那个查询是用来把替罪羊子树对应的权值线段树都翟出来的，底下这个函数就是二分这个翟出来的权值线段树然后二分求第k大的

说到这里我可能知道了多颗权值线段树能够维护静态第k大，或者说，线段树套权值线段树？一会儿去试试，感觉比这个要简单一些

接下来说修改

int modify(int k,int x,int val)
{
    //cout<<"###8"<<endl;
    insert(rt[k],0,70000,val,1);  //在根节点权值线段树插入
    int t,L=a[rt[lch[k]]].sum;
    if(L+1==x) {t=v[k];v[k]=val;}
    else if(L>=x) t=modify(lch[k],x,val);
    else t=modify(rch[k],x-L-1,val);
    insert(rt[k],0,70000,t,-1);
    return t; 
}

修改就是把从根节点到这个修改点所影响的所有线段树进行统一的，插新数，删旧数

最后就是迷之插入了

void insert(int &k,int x,int val)
{
    //cout<<"###10"<<endl;
    if(k==0)  //叶子节点 
    {
        k=++n;
        insert(rt[k],0,70000,val,1);
        v[k]=val;
        return;
    }
    insert(rt[k],0,70000,val,1);
    int L=a[rt[lch[k]]].sum;  //得到当前平衡树节点在权值线段树的坐标 
    if(L>=x) insert(lch[k],x,val);
    else insert(rch[k],x-L-1,val);
    if(a[rt[k]].sum*alpha>max(a[rt[lch[k]]].sum,a[rt[rch[k]]].sum))
    {
        if(gtmp)
        {
            if(lch[k]==gtmp) rebuild(lch[k]);
            else rebuild(rch[k]);
            gtmp=0;
        }
    }
    else gtmp=k;
}

这就是往平衡树里插东西了，插完之后通过权值线段树的sum来看有没有平衡啊，如果没有平衡的话，就重构把

重构的时候不是把替罪羊树变成完全二叉树就完了，还得把里面套的线段树维护好，这里的话

void del(int &k)  //回收替罪羊树 
{
    //cout<<"###6"<<endl;
    if(k==0) return;
    reclaim(rt[k]);  //回收线段树 
    del(lch[k]);p.push_back(k);del(rch[k]);
    k=0;
}
void rebuild(int &k)
{
    //cout<<"###7"<<endl;
    del(k);int s1=p.size();
    for(int i=1;i<=s1;i++) dfn[i]=p[i-1];
    build(k,1,s1);
    p.clear(); 
    
}

线段树直接暴力插进去了，如果要是线段树合并的话，可能还要学一学了，线段树合并是O（logn）的

感谢黄学长

附完整代码：

  1 #include<cstdio>
  2 #include<vector>
  3 #include<iostream>
  4 #include<algorithm>
  5 using namespace std;
  6 const int maxn=70005;
  7 const float alpha=0.75;
  8 int n,m,root,gtmp,sz,lastans;
  9 int v[maxn],dfn[maxn],rt[maxn],lch[maxn],rch[maxn];
 10 //rt是替罪羊节点存的每一个线段树的根节点 
 11 struct seg{int l,r,sum;}a[10000005];
 12 vector<int> rec,t,p;
 13 inline int read()
 14 {
 15     //cout<<"###1"<<endl;
 16     int x=0;
 17     char ch=getchar();
 18     while(ch<'0'||ch>'9') ch=getchar();
 19     while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
 20     return x;
 21 }
 22 inline int newnode()
 23 {
 24     //cout<<"###2"<<endl;
 25     if(rec.size()==0) return ++sz;
 26     else
 27     {
 28         int tmp=rec.back();
 29         rec.pop_back();
 30         return tmp;
 31     }
 32 }
 33 void reclaim(int &k)  //回收叶子的线段树空间
 34 {
 35     //cout<<"###3"<<endl;
 36     if(k==0) return;
 37     rec.push_back(k);
 38     reclaim(a[k].l),reclaim(a[k].r);
 39     a[k].sum=0;k=0; 
 40 }
 41 void insert(int &k,int l,int r,int val,int f)  //每一个替罪羊节点插入权值线段树 
 42 {
 43     //cout<<"###4"<<endl;
 44     if(k==0) k=newnode();
 45     if(l==r) {a[k].sum+=f;return;}
 46     int mid=(l+r)>>1;
 47     if(val<=mid) insert(a[k].l,l,mid,val,f);
 48     else insert(a[k].r,mid+1,r,val,f);
 49     a[k].sum=a[a[k].l].sum+a[a[k].r].sum;
 50     if(a[k].sum==0) reclaim(k); 
 51 } 
 52 void build(int &k,int l,int r)
 53 {
 54     //cout<<"###5"<<endl;
 55     if(l>r) return;
 56     if(l==r)
 57     {
 58         k=dfn[l];
 59         insert(rt[k],0,70000,v[k],1);  //在替罪羊树的叶子节点插入权值线段树 
 60         return;
 61     }
 62     int mid=(l+r)>>1;k=dfn[mid];
 63     build(lch[k],l,mid-1);build(rch[k],mid+1,r);
 64     for(int i=l;i<=r;i++) insert(rt[k],0,70000,v[dfn[i]],1); 
 65 }
 66 void del(int &k)  //回收替罪羊树 
 67 {
 68     //cout<<"###6"<<endl;
 69     if(k==0) return;
 70     reclaim(rt[k]);  //回收线段树 
 71     del(lch[k]);p.push_back(k);del(rch[k]);
 72     k=0;
 73 }
 74 void rebuild(int &k)
 75 {
 76     //cout<<"###7"<<endl;
 77     del(k);int s1=p.size();
 78     for(int i=1;i<=s1;i++) dfn[i]=p[i-1];
 79     build(k,1,s1);
 80     p.clear(); 
 81     
 82 }
 83 int modify(int k,int x,int val)
 84 {
 85     //cout<<"###8"<<endl;
 86     insert(rt[k],0,70000,val,1);  //在根节点权值线段树插入
 87     int t,L=a[rt[lch[k]]].sum;
 88     if(L+1==x) {t=v[k];v[k]=val;}
 89     else if(L>=x) t=modify(lch[k],x,val);
 90     else t=modify(rch[k],x-L-1,val);
 91     insert(rt[k],0,70000,t,-1);
 92     return t; 
 93 }
 94 void query(int k,int l,int r)  //提取出要查询的权值线段树?
 95 {
 96     //cout<<"###8"<<endl;
 97     int L=a[rt[lch[k]]].sum,R=a[rt[k]].sum;
 98     if(l==1&&r==R) {t.push_back(rt[k]);return;}  //要查询的区间映射到了权值线段树 
 99     if(l<=L+1&&r>=L+1) p.push_back(v[k]);  //当前根节点在要查询的区间里 
100     if(r<=L) query(lch[k],l,r);
101     else if(l>L+1) query(rch[k],l-L-1,r-L-1);
102     else
103     {
104         if(l<=L) query(lch[k],l,L);
105         if(R>L+1) query(rch[k],1,r-L-1);
106     }
107 }
108 int solve_query(int L,int R,int K) //二分权值线段树查询区间第k大 ?
109 {
110     //cout<<"###9"<<endl;
111     query(root,L,R);K--;
112     int l=0,r=70000,s1=t.size(),s2=p.size();
113     while(l<r)
114     {
115         int mid=(l+r)>>1,sum=0;
116         for(int i=0;i<s1;i++) sum+=a[a[t[i]].l].sum;
117         for(int i=0;i<s2;i++)
118             if(p[i]>=l&&p[i]<=mid) sum++;
119         if(K<sum)
120         {
121             for(int i=0;i<s1;i++) t[i]=a[t[i]].l;
122             r=mid;
123         }
124         else
125         {
126             for(int i=0;i<s1;i++) t[i]=a[t[i]].r;
127             l=mid+1;K-=sum;
128         }
129     } 
130     t.clear(),p.clear();
131     return l;
132 }
133 void insert(int &k,int x,int val)
134 {
135     //cout<<"###10"<<endl;
136     if(k==0)  //叶子节点 
137     {
138         k=++n;
139         insert(rt[k],0,70000,val,1);
140         v[k]=val;
141         return;
142     }
143     insert(rt[k],0,70000,val,1);
144     int L=a[rt[lch[k]]].sum;  //得到当前平衡树节点在权值线段树的坐标 
145     if(L>=x) insert(lch[k],x,val);
146     else insert(rch[k],x-L-1,val);
147     if(a[rt[k]].sum*alpha>max(a[rt[lch[k]]].sum,a[rt[rch[k]]].sum))
148     {
149         if(gtmp)
150         {
151             if(lch[k]==gtmp) rebuild(lch[k]);
152             else rebuild(rch[k]);
153             gtmp=0;
154         }
155     }
156     else gtmp=k;
157 }
158 int main()
159 {
160     n=read();
161     for(int i=1;i<=n;i++) v[i]=read();
162     for(int i=1;i<=n;i++) dfn[i]=i;
163     build(root,1,n);
164     m=read();
165     int x,y,k;
166     char tmp[5];
167     while(m--)
168     {
169         scanf("%s",tmp);
170         x=read();y=read();x^=lastans;y^=lastans;
171         switch(tmp[0])
172         {
173             case 'Q':k=read();k^=lastans;lastans=solve_query(x,y,k);printf("%d
",lastans);break;
174             case 'M':modify(root,x,y);break;
175             case 'I':gtmp=0;insert(root,x-1,y);
176                 if(gtmp) {gtmp=0;rebuild(root);}
177                 break;
178         }
179     }
180     return 0;
181 }