二叉查找树
在不考虑复杂度的情况下，是一种严格强于线段树的结构。
其结构为左子树小于当前节点，右子树大于当前节点，所以中序遍历就是按全部结点权值大小从小到大遍历。
二叉查找树可支持新增节点，查询一个节点的排名，查询一个排名对应的节点。如果点维护的是权值和，那么可以实现单点修改，区间查询。
但假如每次都插入最小值，树会退化成一条链，每次查找的时间复杂度也就退化为 \(O(n)\)，所以我们需要平衡这棵二叉查找树，由此引入平衡树。
替罪羊树
替罪羊树平衡二叉查找树的方法是当整棵树失衡的时候重构。那何时整棵树才算失衡呢，如下图所示：
发现右子树大小占了整棵树大小的大部分，那么我们就可以设置一个平衡权值 \(\alpha\)，当左子树或右子树的大小大于 \(\alpha \times siz_u\) 的时候，整棵树就是失衡的。这是其中一种失衡情况，另外一种会在后文出现，而 \(\alpha\) 的取值在重构结束会提到。
现在已知一棵子树失衡了，那么如何重构这棵子树且使其满足二叉搜索树的性质呢？我们考虑对这棵子树进行中序遍历，得到的序列必然是权值从小到大排序的序列，此时考虑重构这棵子树的结构。由于需要尽量让该子树平衡，所以每次可以选取该序列中点，当作新的根，然后分别对左子树和右子树进行递归操作，这样既保证了二叉搜索树的性质，又能使树高尽量的小。
中序遍历+重构：
void unfold(int x){if(!x) return;unfold(ls[x]);if(sum_id[x]) rt[++cnt_rt]=x;unfold(rs[x]);return;
}//中序遍历将子树变成序列 #define mid (l+r>>1)void pushup(int x){siz1[x]=siz1[ls[x]]+siz1[rs[x]],//可重集大小(减去了删除的点个数)siz2[x]=siz2[ls[x]]+siz2[rs[x]];//可重集大小(未减去删除的点个数)
}//向上合并int rebuild(int l,int r){if(l>r) return 0;if(l==r) return rt[l];ls[rt[mid]]=rebuild(l,mid-1);rs[rt[mid]]=rebuild(mid+1,r);pushup(rt[mid]);return rt[mid];
}//重构子树，利用类似线段树的方法void bel(int x){cnt_rt=0;unfold(x);rebuild(1,cnt_rt);}//综合重构操作
这样的单次重构的时间复杂度是 \(size(x)\) 的，那么考虑 \(\alpha\) 的取值，首先其肯定要大于 \(0.5\)，因为左右子树大小的最大值肯定大于等于整棵子树大小的 \(0.5\)。其次其不能很小，这样会导致重构次数增加，所以考虑 \(0.7 \sim 1\)。最后其不能太大，因为当一棵树不失衡的情况下，树高最高为 \(\log_{\frac{1}{\alpha}} n\)，当 \(\alpha\) 太大的时候，整棵树的树高会很大，就会导致整棵树每次查找的时间复杂度爆炸。所以一般来说，\(\alpha\) 取 \(0.7 \sim 0.8\) 之间最好。
那么基础操作基本结束，现在就需要解决题目中的问题了，可以参考这个题目要求的问题。
先看操作 \(2\) 也就是删除操作，对于删除操作，我们肯定是找到该点，使其的总副本数减去 \(1\)，然后直接返回。但是发现如果总副本数为 \(0\) 的话该点就不复存在了，留在原地可能会失衡并影响失衡的判断，所以另外一个失衡的判定由此而出，当一棵子树内删除的点大于总子树大小乘 \(1- \alpha\) 时，该子树就是失衡的，所以综上，判定失衡代码即为：
bool check(int x){return fb[x]&&max(tr2[x]*alp<max(tr2[ls[x]],tr2[rs[x]]))||tr1[x]>alp*tr2[x];
}//fb_x 为 x 节点的副本数
现在已经万事具备了，让我们具体解决操作。
- 操作 \(1\)，插入一个数 \(x\)。根据二叉查找树的性质，我们可以很快的找到 \(x\) 应在的位置，如果 \(x\) 以前存在过，那就直接将副本数增加；否则就新开一个节点。
void insert(int &rt,int x){if(!rt){rt=++cnt,fb[rt]=1,tr1[rt]=1,tr2[rt]=1;return;}if(x==val[rt]){fb[rt]++,tr1[rt]++,tr2[rt]++;return;}if(x<val[rt]) insert(ls[rt],x);else insert(rs[rt],x);pushup(rt);
}
- 操作 \(2\)，