簡介
無旋樹堆(一般統稱 \(\text{FHQ-Treap}\))，是一種平衡樹，可以用很少的代碼達到很優秀的復雜度，
前置知識：
- 二叉搜索樹 \(\text{BST}\)
- \(\text{Treap}\) 基本知識
普通平衡樹
例題引入
P6136 【模板】普通平衡樹（資料加強版）
您需要寫一種資料結構，來維護一些整數，其中需要提供以下操作：
- 插入一個整數 \(x\)，
- 洗掉一個整數 \(x\)（若有多個相同的數，只洗掉一個），
- 查詢整數 \(x\) 的排名（排名定義為比當前數小的數的個數 \(+1\)），
- 查詢排名為 \(x\) 的數（如果不存在，則認為是排名小于 \(x\) 的最大數，保證 \(x\) 不會超過當前資料結構中數的總數），
- 求 \(x\) 的前驅（前驅定義為小于 \(x\)，且最大的數），
- 求 \(x\) 的后繼（后繼定義為大于 \(x\)，且最小的數），
本題強制在線，保證所有操作合法（操作 \(2\) 保證存在至少一個 \(x\)，操作 \(4,5,6\) 保證存在答案），
對于 \(100\%\) 的資料，\(1\leq n\leq 10^5\)，\(1\leq m\leq 10^6\)，\(0\leq a_i,x\lt 2^{30}\)，
準備姿勢
const int SIZE = 2e6+5; // 陣列大小
int son[SIZE][2]; // 平衡樹陣列
int val[SIZE],rk[SIZE],siz[SIZE]; // val是權值,rk是隨機權值,siz是子樹大小
int root,points; // root是樹根，points是點數(最后一個節點的編號)
mt19937 randomer(time(0)); // 隨機生成器
#define ls(i) (son[(i)][0]) // 左子樹
#define rs(i) (son[(i)][1]) // 右子樹
void pushup(int i){ // 上推資訊，這里是子樹大小
siz[i]=siz[ls(i)]+siz[rs(i)]+1;
}
int newnode(int v){ // 新建節點
val[++points]=v; // 權值賦值
rk[points]=randomer(); // 隨機生成隨機權值
siz[points]=1; // 散點子樹大小為1
return points; // 回傳節點編號
}
FHQ-Treap 基本操作——分裂(split)
這里的 \(\text{split}\) 是按大小分裂，按權值分裂將會在【文藝平衡樹】中講，
\(\operatorname{split}(p,v,l,r)\) 定義為，將根為 \(p\) 的樹，分裂成兩個子樹 \(l,r\) 使得 \(l\) 的所有點權小于等于 \(v\)，\(r\) 中的所有點權大于 \(v\)，
實作也是非常的暴力，由于BST中，左子樹小于根，右子樹大于根，于是直接判斷，如果 \(p\) 的全職 \(\le v\)，我們就往右子樹遞回看看有沒有機會（左子樹一定滿足），否則就往左子樹遞回，
代碼：
void split(int p,int v,int &left,int &right){
if(!p){ // 節點不存在的情況
left=right=0;
return;
}
if(val[p]<=v){
left=p;
split(rs(p),v,rs(left),right);
}
else{
right=p;
split(ls(p),v,left,ls(right));
}
pushup(p);
}
由于最多一條鏈從根搜到葉子，所以時間復雜度是 \(O(\log n)\) 的，
FHQ-Treap 基本操作——合并(merge)
\(\operatorname{merge}(l,r)\) 指，將 \(l,r\) 兩棵樹合并，然后回傳新的樹的樹根，
如果打過線段樹合并，那么打這一部分的內容會感覺很親切，
在 \(\text{Treap}\) 中，合并方向取決于隨機權值，\(\text{FHQ-Treap}\) 也不例外，
如果 \(l\) 的權值大于 \(r\) 的，那么保留 \(l\) 的左子樹，右子樹改為 \(\operatorname{merge}(r,\operatorname{rightSon}(l))\)，
如果 \(r\) 的權值大于 \(l\) 的，那么保留 \(r\) 的左子樹，右子樹改為 \(\operatorname{merge}(l,\operatorname{rightSon}(r))\)，
代碼：
int merge(int left,int right){
if(!left||!right){ // 節點不存在的情況
if(left)return left;
else if(right)return right;
else return 0;
}
if(rk[left]<rk[right]){
ls(right)=merge(left,ls(right));
pushup(right);
return right;
}
else{
rs(left)=merge(rs(left),right);
pushup(left);
return left;
}
}
時間復雜度 \(O(\log n)\)，
FHQ-Treap 其他操作——insert
\(\operatorname{insert}(v)\)，在平衡樹中插入一個數 \(v\)，
我們可以將平衡樹分裂成兩個部分 \(x,y\)，使得 \(x\lt v,y \ge v\)，然后合并回去，
代碼：
void insert(int v){
int left=0,right=0;
split(root,v-1,left,right);
root=merge(merge(left,newnode(v)),right);
}
FHQ-Treap 其他操作——remove
\(\operatorname{remove}(v)\)，在平衡樹中洗掉元素 \(v\)，如果有多個，洗掉其中的任意一個，
將平衡樹分裂成 \(x,y,z\)，使得 \(x\lt v,y=v,z\gt v\)，將 \(y\) 的根刪掉，然后合并 \(x,y,z\)，
代碼：
void remove(int v){
int left=0,mid=0,right=0;
split(root,v,left,right);
split(left,v-1,left,mid);
mid=merge(ls(mid),rs(mid));
root=merge(merge(left,mid),right);
}
FHQ-Treap 的其他操作——rank
\(\operatorname{rank}(v)\)，查詢 \(v\) 在平衡樹中的排名，
先將平衡樹分裂成 \(x,y\)，使得 \(x\lt v,y \ge v\)，然后查詢 \(x\) 的子樹大小，加 \(1\) 就是答案，最后記得合并回去，
代碼：
int rnk(int v){
int left=0,right=0,ret;
split(root,v-1,left,right);
ret=siz[left]+1;
root=merge(left,right);
return ret;
}
FHQ-Treap 的其他操作——kth,pre,nxt
由于本人弱，不想講解，
代碼：
int kth(int k){
int now=root;
while(1){
if(k<=siz[ls(now)]){
now=ls(now);
}
else if(k==siz[ls(now)]+1){
return val[now];
}
else{
k-=siz[ls(now)]+1;
now=rs(now);
}
}
}
int pre(int v){
int now=root,ret=0;
while(1){
if(!now){
return ret;
}
else if(v<=val[now]){
now=ls(now);
}
else{
ret=val[now];
now=rs(now);
}
}
}
int next(int v){
int now=root,ret=0;
while(1){
if(!now){
return ret;
}
else if(v>=val[now]){
now=rs(now);
}
else{
ret=val[now];
now=ls(now);
}
}
}
例題代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace FHQTreap{
const int SIZE = 2e6+5;
int son[SIZE][2];
int val[SIZE],rk[SIZE],siz[SIZE],root,points;
mt19937 randomer(time(0));
#define ls(i) (son[(i)][0])
#define rs(i) (son[(i)][1])
void pushup(int i){
siz[i]=siz[ls(i)]+siz[rs(i)]+1;
}
int newnode(int v){
val[++points]=v;
rk[points]=randomer();
siz[points]=1;
return points;
}
void split(int p,int v,int &left,int &right){
if(!p){
left=right=0;
return;
}
if(val[p]<=v){
left=p;
split(rs(p),v,rs(left),right);
}
else{
right=p;
split(ls(p),v,left,ls(right));
}
pushup(p);
}
int merge(int left,int right){
if(!left||!right){
if(left)return left;
else if(right)return right;
else return 0;
}
if(rk[left]<rk[right]){
ls(right)=merge(left,ls(right));
pushup(right);
return right;
}
else{
rs(left)=merge(rs(left),right);
pushup(left);
return left;
}
}
void insert(int v){
int left=0,right=0;
split(root,v-1,left,right);
root=merge(merge(left,newnode(v)),right);
}
void remove(int v){
int left=0,mid=0,right=0;
split(root,v,left,right);
split(left,v-1,left,mid);
mid=merge(ls(mid),rs(mid));
root=merge(merge(left,mid),right);
}
int kth(int k){
int now=root;
while(1){
if(k<=siz[ls(now)]){
now=ls(now);
}
else if(k==siz[ls(now)]+1){
return val[now];
}
else{
k-=siz[ls(now)]+1;
now=rs(now);
}
}
}
int pre(int v){
int now=root,ret=0;
while(1){
if(!now){
return ret;
}
else if(v<=val[now]){
now=ls(now);
}
else{
ret=val[now];
now=rs(now);
}
}
}
int next(int v){
int now=root,ret=0;
while(1){
if(!now){
return ret;
}
else if(v>=val[now]){
now=rs(now);
}
else{
ret=val[now];
now=ls(now);
}
}
}
int rnk(int v){
int left=0,right=0,ret;
split(root,v-1,left,right);
ret=siz[left]+1;
root=merge(left,right);
return ret;
}
}
namespace solution{
int n,m,lastans,ret;
int solution(){
lastans=0;
ret=0;
cin>>n>>m;
for(int i=1,v;i<=n;i++){
cin>>v;
FHQTreap::insert(v);
}
while(m--){
int op,v;
cin>>op>>v;
if(op==1){
v^=lastans;
FHQTreap::insert(v);
}
else if(op==2){
v^=lastans;
FHQTreap::remove(v);
}
else if(op==3){
v^=lastans;
lastans=FHQTreap::rnk(v);
ret^=lastans;
}
else if(op==4){
v^=lastans;
lastans=FHQTreap::kth(v);
ret^=lastans;
}
else if(op==5){
v^=lastans;
lastans=FHQTreap::pre(v);
ret^=lastans;
}
else{
v^=lastans;
lastans=FHQTreap::next(v);
ret^=lastans;
}
}
cout<<ret;
return 0;
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
return solution::solution();
}
AC Record
普通平衡樹例題
P2343 寶石管理系統
P2343 寶石管理系統
GY 君購買了一批寶石放進了倉庫，有一天 GY 君心血來潮，想要清點他的寶石，于是把 \(m\) 個寶石都取出來放進了寶石管理系統，每個寶石 \(i\) 都有一個珍貴值 \(v_i\)，他希望你能撰寫程式查找到從大到小第 \(n\) 珍貴的寶石，但是現在問題來了，他非常不小心的留了一些寶石在倉庫里面，有可能要往現有的系統中添加寶石，這些寶石的個數比較少，他表示非常抱歉，但是還是希望你的系統能起作用，\(m\leq 100000\),\(q\leq 30000\)
這道題比較水，直接 \(\text{FHQ-Treap}\) 模擬，
時間復雜度 \(O(q\log m)\)
P2073 送花
見這里
P1503 鬼子進村
見這里
P3871 [TJOI2010]中位數
見這里
如果文章有問題，靜待斧正，建議向我發送洛谷私信并指出博文地址 https://www.cnblogs.com/zheyuanxie/p/fhq-treap.html！轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509339.html
標籤：其他
上一篇：轉載：潘天佑：改變我人生的8本書
下一篇：leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 從前序與中序遍歷序列構造二叉樹(中等)