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

# $Scapegoat Tree$(替罪羊树) **网上许多题解都不是完整的替罪羊树** 一个完整的替罪羊树还需做到以下两点 1、删除时需要对根节点进行过多cnt==0节点的判断  2、重构子树时没有及时更新父亲的cover值 来一发最为正确的实现了rankTree的替罪羊树题解 O2跑了151ms,不加优化也有250ms [无O2](https://www.luogu.org/recordnew/show/13173573) | [O2](https://www.luogu.org/record/show?rid=13173548) ~~还没完全实现常数优化~~ ~~本人感觉好好背~~ ### 替罪羊树原理以及实现前完备性讨论 替罪羊树属于暴力重构平衡树。 其维护平衡手段就是暴力重构。 暴力重构(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; } }; ``` ### 内存池优化 ```cpp 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就好写了 ```cpp 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](https://www.luogu.org/paste/zwf94s8p) ### Thanks [某不存在百科网站](https://zh.wikipedia.org/) [某英语百科网站](https://en.wikipedia.org/) [ g1n0st的SGT教程](https://zhuanlan.zhihu.com/p/21263304)