\(Scapegoat Tree\)(替罪羊树)
网上许多题解都不是完整的替罪羊树
一个完整的替罪羊树还需做到以下两点
1、删除时需要对根节点进行过多cnt==0节点的判断
2、重构子树时没有及时更新父亲的cover值
来一发最为正确的实现了rankTree的替罪羊树题解
O2跑了151ms,不加优化也有250ms
还没完全实现常数优化
本人感觉好好背
替罪羊树原理以及实现前完备性讨论
替罪羊树属于暴力重构平衡树。
其维护平衡手段就是暴力重构。
暴力重构(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更棒
};