平衡树学习笔记
Stars_visitor_tyw
·
2025-02-16 14:08:39
·
算法·理论
平衡树
通常是指二叉搜索平衡树。
概念解释——二叉搜索树
对于一棵二叉树，每个点 i 有权值 w_i，对于任意点 x，其左子树的权值都不超过 w_x，其右子树的权值都大于 w_x。
我们常常将一个序列的下标当作权值构建二叉搜索树，这样树的中序遍历就是一段连续的区间。
平衡树的广泛定义
是指一棵树型结构，对任意结点 x，其左右子树的高度差不超过 1。
算法竞赛中平衡树的实现
treap，随机，左旋和右旋。
splay，贪心，伸展和旋转。
fhq_treap（无旋 treap），分裂+合并。
fhq_treap 的实现
分裂操作，split。
给定一棵平衡树 k，按照某个权值 val，分裂成平衡树 a 和 b，且 a 树所有点的权值不超过 val，b 树的所有点权大于 val。
合并操作，merge。
将两棵平衡树 a 和 b 合并成一棵平衡树 k，且保证 a 树的点权都小于 b 树的点权。
代码
#include
#define int long long
using namespace std;
const int INT=1145141919810;
#define N 500005
int n, tot, root;
struct node
{
int val, rnk, lc, rc, siz;
}tree[N];
void pushup(int k)
{
tree[k].siz=tree[tree[k].lc].siz+tree[tree[k].rc].siz+1;
}
int add_node(int val)
{
tree[++tot].siz=1;
tree[tot].val=val;
tree[tot].lc=tree[tot].rc=0;
tree[tot].rnk=rand();
return tot;
}
void split(int k, int &a, int &b, int val)
{
if(!k)
{
a=b=0;
return ;
}
if(tree[k].val<=val)
{
a=k;
split(tree[k].rc,tree[k].rc,b,val);
}
else
{
b=k;
split(tree[k].lc,a,tree[k].lc,val);
}
pushup(k);
}
void merge(int &k, int a, int b)
{
if(!a||!b)
{
k=a+b;
return ;
}
if(tree[a].rnk { k=a; merge(tree[a].rc,tree[a].rc,b); } else { k=b; merge(tree[b].lc,a,tree[b].lc); } pushup(k); } void insert(int &k, int val) { int a=0, b=0, cur=add_node(val); split(k,a,b,val); merge(a,a,cur); merge(k,a,b); return ; } void del(int &k, int val) { int a=0, b=0, z=0; split(k,a,b,val); split(a,a,z,val-1); merge(z,tree[z].lc,tree[z].rc); merge(a,a,z); merge(k,a,b); return ; } int find_rank(int &k, int val) { int a=0, b=0; split(k,a,b,val-1); int tmp=tree[a].siz+1; merge(k,a,b); return tmp; } int find_num(int k ,int x) { while(tree[tree[k].lc].siz+1!=x) { if(tree[tree[k].lc].siz>=x)k=tree[k].lc; else { x-=tree[tree[k].lc].siz+1; k=tree[k].rc; } } return tree[k].val; } int calc_prev(int &k, int val) { int a=0, b=0; split(k,a,b,val-1); int tmp=find_num(a,tree[a].siz); merge(k,a,b); return tmp; } int calc_suf(int &k, int val) { int a=0, b=0; split(k,a,b,val); int tmp=find_num(b,1); merge(k,a,b); return tmp; } signed main() { cin>>n; root=0; srand(time(0)); for(int i=1;i<=n;i++) { int op, val; cin>>op>>val; if(op==1) { insert(root,val); } else if(op==2) { del(root,val); } else if(op==3) { cout< } else if(op==4) { cout< } else if(op==5) { cout< } else if(op==6) { cout< } } } 文艺平衡树 P3391 无旋 treap 按 size 分裂 适用于处理序列的区间问题，比如将数列 [L,R] 翻转。 将下标视为结点的权值，按下标建立平衡树，其中序遍历为连续下标。 split 时，将平衡树分裂成 A 和 B 两棵树，且 a 树的结点恰好为 x 个。 模板思路 以下标为点权，建立平衡树。 对于操作区间 [L,R] 可以将平衡树上对应的子树准确分裂。一个区间的翻转等价于一棵树的左右子树的迭代翻转。 为了节省时间，每个结点维护懒标记 tag_i 表示以 i 为根的子树是否需要翻转。 打标记：tag_i=tag_i \oplus i。下传标记的时间：分裂、合并、输出前。 P3850 书架 把位置和排名对应起来理解。 初始时 n 本书排名 1\sim n 建树。 插入一本书位置为 x 时，分裂 x 个结点，将新的书放在右侧合并。 P3765 总统选举 前置知识——摩尔投票法 求出数列中是否有出现次数超过一半的元素。 维护 ans 表示目标元素，维护 cnt 表示目标元素出现的次数。 伪代码： ... for(int i=1;i<=n;i++) { if(!cnt)ans=a[i],cnt++; else if(a[i]==ans)cnt++; else cnt--; } if(cnt>0)cout< else cout<<"No solution."; ... 思路 利用摩尔投票在有解时，可以找到超过一半的元素。 利用线段树分治维护摩尔投票的信息，对于一个结点 cur，其左右子树若 ans1==ans2，则 ans=ans1+ans2,cnt=cnt1+cnt2。否则 ans=cnt1>cnt2?ans1:ans2,cnt=abs(cnt1-cnt2)。 如何确保区间内找到的 ans 确实超过了一半？ 对于每个候选人 i，维护一棵平衡树 tr_i 表示投票给 i 的人，按下标左小右大构建。 对于询问 [L,R]，利用线段树得到众数 ans，找到 ans 对应的平衡树，分裂出 [L,R] 的部分，设有 size 结点，若 2\times size>(R-L+1)，则 ans 超过一半。 对于修改操作，直接将结点从一棵树 merge 到另一棵树。 P5217 贫穷 I 操作，tot++，插入结点，编号和点权 tot。 D 操作，split 前 x 个，split 前 x-1 个，丢掉。 R 操作，参照文艺平衡树，打标记，翻转。 P 操作，找排名为 x 的元素，从根结点开始，要么往左，要么往右，找到 x 后，取出当前平衡树中 x 的左子树的大小。 T 操作，分裂 x，再分裂 x-1。 Q 操作，考虑到字母只有 26 个，状压维护。对于平衡树结点 cur，buc[cur]=buc[lc]|buc[rc]。