• rt,对于求区间排名，lz写了两种写法，但是在堆空间不变的情况下内存耗费天差地别，请问是为什么？

方法一

内存：512+MB（MLE了）

//省略
int Sum(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return T[rt].cnt;
    int mid=(l+r)>>1;
    int res=0;
    if(L<=mid) res+=Sum(T[rt].lc,l,mid,L,R);
    if(R>mid) res+=Sum(T[rt].rc,mid+1,r,L,R);
    return res;
}
//省略
void Get(int l,int r)
{
    ln=rn=0;
    for(int i=l-1;i;i-=lowbit(i)) Lt[++ln]=Root[i];
    for(int i=r;i;i-=lowbit(i)) Rt[++rn]=Root[i];
}
int Rank(int l,int r,int x)
{
    Get(l,r);
    int res=0;
    for(int i=1;i<=rn;i++) res+=Sum(Rt[i],1,Dsiz,1,x-1);
    for(int i=1;i<=ln;i++) res-=Sum(Lt[i],1,Dsiz,1,x-1);
    return res+1;
}

方法二

内存：150MB

//省略
int Rank(int l,int r,int x)
{
    Get(l,r);
    int L=1,R=Dsiz;
    int res=0;
    while(L<R)
    {
        int mid=(L+R)>>1;
        if(x<=mid)
        {
            for(int i=1;i<=rn;i++) Rt[i]=T[Rt[i]].lc;
            for(int i=1;i<=ln;i++) Lt[i]=T[Lt[i]].lc;
            R=mid;
        }
        else
        {
            
            for(int i=1;i<=rn;i++) res+=T[T[Rt[i]].lc].cnt;
            for(int i=1;i<=ln;i++) res-=T[T[Lt[i]].lc].cnt;
            for(int i=1;i<=rn;i++) Rt[i]=T[Rt[i]].rc;
            for(int i=1;i<=ln;i++) Lt[i]=T[Lt[i]].rc;
            L=mid+1;
        }
    }
    return res+1;
}