替罪羊树小学习
2026-01-27 21:39:29
发布于：广东
32阅读
0回复
0点赞
upd：暴力推平的复杂度分数写反了。
调了 10h 的 FHQ-Treap 调疯了，然后直接加入邪修（
替罪羊树是一个比较暴力的平衡树。
首先我们复习一下普通二叉树是怎么加入元素的：
- 如果已经遍历到不存在的节点了，就新开一个节点。
- 如果当前节点的值恰好是要修改的值，就修改。
- 否则如果要修改的值小于当前节点的值，就往左子树搜。
- 否则往右子树搜。
- 然后
push_up合并左右子树及当前节点的信息。
void push_up(node *cur){
cur -> siz = cur -> val;
if(cur -> lson) cur -> siz += cur -> lson -> siz;
if(cur -> rson) cur -> siz += cur -> rson -> siz;
}
void _modify(node *&cur, T k, T v){
if(!cur){
cur = new node(k, v);
return;
}
if(cur -> key == k){
cur -> val += v;
cur -> siz += v;
return;
}
if(cur -> key > k) _modify(cur -> lson, k, v);
else _modify(cur -> rson, k, v);
push_up(cur);
}
这样子会有什么问题呢？
注意到出题人可能会构造数据，让你建出一个十分不平衡的二叉树，然后就炸了。显然单次查询最坏可以卡到 。
那不平衡怎么办呢？把它弄平衡呗。
我们可以在修改的时候判断当前节点，如果发现这个节点不太平衡了，就直接暴力把这个子树重构成一个最平衡的完全二叉树。
判断一个节点不平衡的方法有很多种，我这里用的是比较子树节点个数。
定义 为节点 的子树节点数量，如果 ，那么就将他看做不平衡，其中 是一个 的数。
这么做为什么是对的呢？
首先考虑查询复杂度。
由于某儿子的 大于等于父亲的 的 倍就会被重构，所以在每次操作后一定满足两个子树的 小于父亲的 。而查询就是递归到 的点，所以时间复杂度是 的。
然后看看暴力重构复杂度。
假设一个节点的子树当前处于完全平衡状态（），则解方程可得至少增加 个节点才能使得它被 重构，然后又处于平衡状态。均摊时间复杂度为 。
所以只要 不设得太离谱这个复杂度就是 的。
直接贴代码。
namespace cjdst{
template <typename T>
class Goat_Tree{
const double B = 0.75;
class node{
public:
T key, val;
T siz, realsiz;
node *lson, *rson;
node(){}
node(T k, T v){
key = k, val = v, siz = v;
realsiz = 1;
lson = rson = 0;
}
}*root;
void push_up(node *cur){
cur -> siz = cur -> val;
cur -> realsiz = 1;
if(cur -> lson){
cur -> siz += cur -> lson -> siz;
cur -> realsiz += cur -> lson -> realsiz;
}
if(cur -> rson){
cur -> siz += cur -> rson -> siz;
cur -> realsiz += cur -> rson -> realsiz;
}
}
void get_subtree(node *cur, std::vector <T> &k, std::vector <T> &v){
if(!cur) return;
get_subtree(cur -> lson, k, v);
k.push_back(cur -> key);
v.push_back(cur -> val);
get_subtree(cur -> rson, k, v);
}
node *_rebuild(std::vector <T> &k, std::vector <T> &v, int l, int r, node *cur){
if(l > r) return 0;
int mid = (l + r) >> 1;
if(!cur) cur = new node(k[mid], v[mid]);
else (*cur) = node(k[mid], v[mid]);
cur -> lson = _rebuild(k, v, l, mid - 1, 0);
cur -> rson = _rebuild(k, v, mid + 1, r, 0);
push_up(cur);
return cur;
}
void rebuild(node *cur){
std::vector <T> k, v;
get_subtree(cur, k, v);
_rebuild(k, v, 0, k.size() - 1, cur);
}
node *_modify(node *&cur, T k, T v){
if(!cur){
cur = new node(k, v);
return 0;
}
if(cur -> key == k){
cur -> val += v;
cur -> siz += v;
return 0;
}
node *ans = 0;
if(cur -> key > k) ans = _modify(cur -> lson, k, v);
else ans = _modify(cur -> rson, k, v);
push_up(cur);
if((cur -> lson && cur -> lson -> realsiz >= cur -> realsiz * B) ||
(cur -> rson && cur -> rson -> realsiz >= cur -> realsiz * B)) ans = cur;
return ans;
}
public:
Goat_Tree(){root = 0;}
void modify(T k, T v){
node *cur = _modify(root, k, v);
if(cur) rebuild(cur);
}
T get_rank(T k){
node *cur = root;
ll ans = 0;
while(cur){
if(cur -> key > k){
cur = cur -> lson;
continue;
}
if(cur -> lson) ans += cur -> lson -> siz;
if(cur -> key == k) return ans + 1;
ans += cur -> val;
cur = cur -> rson;
}
return ans + 1;
}
T nth_element(T k){
node *cur = root;
while(k){
if(cur -> lson){
if(cur -> lson -> siz >= k){
cur = cur -> lson;
continue;
}
k -= cur -> lson -> siz;
}
if(cur -> val >= k) return cur -> key;
k -= cur -> val;
cur = cur -> rson;
}
return cur -> key;
}
T get_pre(T val){
return nth_element(get_rank(val) - 1);
}
T get_next(T val){
return nth_element(get_rank(val + 1));
}
};
}
有帮助，赞一个