z3475 的博客

题解 P3369 【【模板】普通平衡树】

$Scapegoat Tree$(替罪羊树)

网上许多题解都不是完整的替罪羊树

一个完整的替罪羊树还需做到以下两点

1、删除时需要对根节点进行过多cnt==0节点的判断

删除重构

2、重构子树时没有及时更新父亲的cover值

来一发最为正确的实现了rankTree的替罪羊树题解

O2跑了151ms,不加优化也有250ms

无O2 | O2

还没完全实现常数优化

本人感觉好好背

替罪羊树原理以及实现前完备性讨论

替罪羊树属于暴力重构平衡树。

其维护平衡手段就是暴力重构。

暴力重构(rebuild):把一个树中序遍历得到排序后数组,再对这个数组实施类似建线段树的建二叉搜索树的过程,就得到了完美的二叉搜索树。

替罪羊树有性质1: 对于任意一个节点node都有$$max(size(lson),size(rson))\le size(node)*alpha$$ size指这颗子树的节点数量,alpha为预定义常数

插入

回溯时就对于每个节点判断这个式子是否成立,不成立就rebuild

但是如果父节点rebuild了,子节点就不必rebuild了,所以我们在回溯时用一个变量存需要重构的最最最上的节点,insert完毕后rebuild即可

删除

替罪羊树删除是把每个节点打上已删除标记,然后再在rebuild(准确来说是压扁)时删除

我们不妨扩展这个标记到副本数,这样就可以方便实现RankTree操作了(甚至维护区间)

但是上面size的定义就变了啊,我们就把上面size变成另一个变量cover就可以了嘛

然后又有两个问题出现了

1、如果删除节点过多导致整棵树有着巨多的空节点,我们还需对每个节点加个rsize域表示当前子树中实际存在的节点数量,每次erase时判断根节点满不满足上述条件,不满足就rebuild根节点

2、插入过程中,对一个子树进行rebuild,这个子树根节点的cover值可能会变(rebuild删掉了嘛),我们就利用上述rsize域,打上需重构标记前把rsize给cover即可防止此现象,因为这时的cover才是正确的cover

查找k大&多少个比x小

同二叉查找树的kth&rank操作

代码实现

alpha&beta&节点定义

这里我瞎BB了一个常量beta,用于删除后判断子树是否有过多cnt==0节点

alpha趋近于1时,整棵树就是个BST

alpha趋近于0.5,整棵树趋近于完全平衡,但是rebuild次数急剧增多

可用来控制修改密集型和查找密集型数据

实践证明当插入和查询kth操作为1:3比重时,alpha=0.75最快。1:1时则偏向0.85

取中间值0.8即可

如果查找操作较多,alpha建议取0.7

const double alpha=0.8;
const double beta=0.35;

rsize和上述定义一致,用于存储子树真实存在(cnt!=0)的节点,可用于判断子树是否有足够的cnt==0节点以及重构更新cover用(rmaintain函数)

template<class T,class iT>
struct node{//T为值类型,iT为索引值类型
    T val;//值
    iT cnt,size,cover,rsize;//cnt值数量,size子树数量,cover子树节点数量
    node *ch[2];//左儿子,右儿子
    node (T v,iT c){val=v;cnt=size=c;rsize=(c!=0);cover=1;}
    inline void maintain(){//调整
                    size=cnt+ch[0]->size+ch[1]->size;
                    rsize=(cnt!=0?1:0)+ch[0]->rsize+ch[1]->rsize;
                    cover=1+ch[0]->cover+ch[1]->cover;}
    inline void rmaintain(){maintain();cover=rsize;}//用于重构时调整
    inline bool isBad(){return max(ch[0]->cover,ch[1]->cover)>
                        (alpha*cover+0.4);}//判断是不是替罪羊
    inline char cmp(T v){//比较&返回,char压位
        if (v==val) return -1;
        return v>=val;
    }
    inline char cmpkth(iT &k){//比较k大&修改k
        iT p=k-ch[0]->size;
        if (p<=0) return 0;
        k=p;p-=cnt;
        if (p<=0) return -1;
        k=p;return 1;
    }
};

内存池优化

template<class T>
struct mem_pool{
    T *begin,*end,**clr;//begin,end表示当前池区间,前开后闭
                        //clr表示替罪羊树reBuild时临时数组
    unsigned long long s;//当前池的总size
    queue<T*> gc;//垃圾回收器,存放删除节点,可重复利用内存空间
    void extend(){s<<=1;end=(begin=(T*)malloc(sizeof(T)*s))+s;}//倍增扩展池
    inline mem_pool(){//构造函数
        s=1<<15;extend();
        clr=(T**)malloc(sizeof(T*)*100010);
    }
    inline T* New(T a){//new
        T *ans;
        if (gc.empty()){
            *(ans=begin)=a;
            if (++begin==end) extend();//当前池用完,扩展
        }else{//用垃圾回收器
            *(ans=gc.front())=a;
            gc.pop();
        }
        return ans;
    }
    inline void Del(T *a){gc.push(a);}//delete
};

倍增,保证空间复杂度O(n)动态增长

考场上面还是打个简单点的吧

SGT构造函数&Rebuild

    Tnode **to;//待重构节点,因为要改变一个指针,所以要用双重指针
    T v;iT s;//待加入/删除节点权值和size
    inline void insert(Tnode *&e){//递归插入
        if (e==nil){
            e=alloc->New(Tnode(v,s));
            e->ch[0]=e->ch[1]=nil;
            return ;
        }
        char d=e->cmp(v);//char压位
        if (d==-1)
            e->cnt+=s;
        else insert(e->ch[d]);
        //回溯调整
        if (e->isBad()) to=&e,e->rmaintain();//rsize覆盖cover,可传正确cover给祖先节点
        else e->maintain();
    }

    inline void erase(Tnode *&e){//递归删除
        if (e==nil) exit(-1);//没找到,强行退出XD
        char d=e->cmp(v);
        if (d==-1)
            e->cnt=max(0,e->cnt-s);//为了防止非法调用
        else erase(e->ch[d]);
        e->maintain();
    }

    inline void insert(T vs,iT ss){//对上述递归插入简单封装
        v=vs;s=ss;
        to=&nil;
        insert(head);
        reBuild(*to);
    }

    inline void erase(T vs,iT ss){//同上
        v=vs;s=ss;
        erase(head);
        if ((head->cover-head->rsize)>head->cover*beta)//如果cnt!=0节点过多
            reBuild(head);
    }
    }

Rank&Kth

有了cmp&cmpkth就好写了

    inline iT rank(T v){
        Tnode *e=head;iT k=1;char d;
        while (e!=nil&&(d=e->cmp(v))!=-1){
            if (d==1) k+=e->ch[0]->size+e->cnt;//右走累加
            e=e->ch[d];
        }
        return k+e->ch[0]->size;//返回前别忘了左子树
    }

    inline Tnode* kth(iT k){
        Tnode *e=head;char d;
        while ((d=e->cmpkth(k))!=-1) e=e->ch[d];//cmpkth帮我们做了减法
        return e;
    }
    #undef Tnode//define后undef更棒
};

register&inline优化总代码

LuoguPaste

Thanks

某不存在百科网站

某英语百科网站

g1n0st的SGT教程


2018-11-04 21:05:57 in 题解