重量平衡树学习笔记

发布于 2021-06-27 | 分类于平衡树、学习笔记 | 2分钟 | 472字数 | 浏览量：

重量平衡树

一棵单次操作影响最大子树大小均摊/期望较小的平衡树

显然，根据定义，我们能支持在平衡树上维护一些与子树有关的信息

在重量平衡树上，我们当做旋转操作后，对其进行暴力重构的复杂度可以接受

在OI领域，我们一般常用的重量平衡树非旋的替罪羊树或者基于旋转的treap

对于插入操作，不妨设点 $x$ 最终旋转到了祖先 $p$ ，那么代表点 $x$ 的权值是子树 $p$ 中最小的

概率为 $\frac 1 {siz_p}$ ，重构一次整个子树 $p$ 代价为 $siz_p$ 故期望代价为 $1$

又因为treap的期望高度为 $logn$ ，则期望 $logn$ 次代价，故期望复杂度为 $O(logn)$

对于删除操作，考虑直接重构子树 $x$

由于点的期望高度是 $logn$ ，易得点的期望子树大小为 $logn$

所以期望复杂度为 $O(logn)$

对于平衡树上的两点比较大小（并非容易比较的简单权值），普通平衡树是 $O(logn)$ 的

重量平衡树通过维护动态下标可以做到 $O(1)$ 查询

对于每一个点赋予一个实数区间 $(l,r)$ ，其左儿子分配 $(l,\frac{l+r}2)$ ，右儿子 $(\frac {l+r}2,r)$

对于旋转操作每次给子树内重新分配下标，可通过比较两点区间中点比较大小

重量平衡树支持套上维护子树信息的其它树，例如线段树

复杂度是一般是 $O(nlog^2n)$