首页 > 其他分享 >Treap

Treap

时间：2023-08-12 22:56:34浏览次数：30  
标签：val rs int tr Treap ls define

BST

\(v_i\) 表示点权，\(x\) 表示当前点，\(L\) 表示左子树，\(R\) 表示右子树

在普通二叉树的基础上多一个条件

对于 \(p\in L\)，满足 \(v_p\leq v_x\)

对于 \(q\in R\)，满足 \(v_x<v_q\)

Treap

但是这样如果 BST 是一条链的话就退化 \(O(n)\)，而且很容易卡，考虑Treap

Treap 就是在普通 BST 基础上加上随机点权，随机点权满足堆性质，这样通过随机的堆可以保证树的均匀，即时间复杂度稳定

旋转 Treap

#include<bits/stdc++.h>

using namespace std;


struct node {
    int ls, rs;
    int val, dat;
    int cnt, siz;
    #define ls(p) tr[p].ls
    #define rs(p) tr[p].rs
    #define v(p) tr[p].val
    #define d(p) tr[p].dat
    #define c(p) tr[p].cnt
    #define s(p) tr[p].siz
};

const int INF=1<<30;
struct treap {
    int top, rt;
    vector<node> tr;
    int nnew(int val) {
        v(++top)=val;
        d(top)=rand();
        c(top)=s(top)=1;
        return top;
    }
    void pushup(int p) {
        s(p)=s(ls(p))+s(rs(p))+c(p);
    }
    void build(int siz) {
    	tr.resize(siz+1);
        rt=nnew(-INF);
        rs(rt)=nnew(INF);
        pushup(rt);
    }
    int getrk(int p,int val) {
        if(p==0) return 0;
        if(val==v(p)) return s(ls(p))+1;
        if(val<v(p)) return getrk(ls(p),val);
        return getrk(rs(p),val)+s(ls(p))+c(p);
    }
    int getrk(int val) {
    	return getrk(rt,val)-1;
    }
    int getval(int p,int rk) {
        if(p==0) return INF;
        if(rk<=s(ls(p))) return getval(ls(p),rk);
        if(rk<=s(ls(p))+c(p)) return v(p);
        return getval(rs(p),rk-s(ls(p))-c(p)); 
    }
    int getval(int rk) {
    	return getval(rt,rk+1);
    }
    void uplt(int &p) {
        int q=ls(p);
        ls(p)=rs(q), rs(q)=p, p=q;
        pushup(rs(p)), pushup(p);
    }
    void uprt(int &p) {
        int q=rs(p);
        rs(p)=ls(q), ls(q)=p, p=q;
        pushup(ls(p)), pushup(p);
    }
    void insert(int &p,int val) {
        if(p==0) {
            p=nnew(val);
            return;
        }
        if(val==v(p)) {
            c(p)++, pushup(p);
            return;
        }
        if(val<v(p)) {
            insert(ls(p),val);
            if(d(p)<d(ls(p))) uplt(p);
        }
        else {
            insert(rs(p),val);
            if(d(p)<d(rs(p))) uprt(p);
        }
        pushup(p);
    }
    void insert(int val) {
    	insert(rt,val);
    }
    int getpre(int val) {
        int ans=1, p=rt;
        for( ; p; p=val<v(p)?ls(p):rs(p)) {
            if(val==v(p)) {
                if(ls(p)) {
                    for(p=ls(p); rs(p); p=rs(p));
                    ans=p;
                }
                break;
            }
            if(v(p)<val&&v(p)>v(ans)) ans=p;
        }
        return v(ans);
    }
    int getnxt(int val) {
        int ans=2, p=rt;
        for( ; p; p=val<v(p)?ls(p):rs(p)) {
            if(v(p)==val) {
                if(rs(p)) {
                    for(p=rs(p); ls(p); p=ls(p));
                    ans=p;
                }
                break;
            }
            if(v(p)>val&&v(p)<v(ans)) ans=p;
        }
        return v(ans);
    }
    void remove(int &p,int val) {
        if(p==0) return;
        if(val==v(p)) {
            if(c(p)>1) {
                c(p)--, pushup(p);
                return;
            } 
            if(ls(p)||rs(p)) {
                if(rs(p)==0||d(ls(p))>d(rs(p)))
                    uplt(p), remove(rs(p),val);
                else uprt(p), remove(ls(p),val);
                pushup(p); 
            }
            else p=0;
            return;
        }
        val<v(p)?remove(ls(p),val):remove(rs(p),val);
        pushup(p);
    }
	void remove(int val) {
		remove(rt,val);
	}
} qwq;

#include<bits/stdc++.h>
#define int long long
#define MN 101000 

using namespace std;

struct node {
	int ls, rs;
	int val, dat;
	int cnt, siz;
	#define ls(p) tr[p].ls
	#define rs(p) tr[p].rs
	#define v(p) tr[p].val
	#define d(p) tr[p].dat
	#define c(p) tr[p].cnt
	#define s(p) tr[p].siz
} tr[MN]; 

const int INF=(int)1<<60;
int top, rt;

int nnew(int val) {
	v(++top)=val;
	d(top)=rand();
	c(top)=s(top)=1;
	return top;
}

void pushup(int p) {
	s(p)=s(ls(p))+s(rs(p))+c(p);
}

void build() {
	rt=nnew(-INF);
	rs(rt)=nnew(INF);
	pushup(rt);
}

int getrk(int p,int val) {
	if(p==0) return 0;
	if(val==v(p)) return s(ls(p))+1;
	if(val<v(p)) return getrk(ls(p),val);
	return getrk(rs(p),val)+s(ls(p))+c(p);
}

int getval(int p,int rk) {
	if(p==0) return INF;
	if(rk<=s(ls(p))) return getval(ls(p),rk);
	if(rk<=s(ls(p))+c(p)) return v(p);
	return getval(rs(p),rk-s(ls(p))-c(p)); 
}

void uplt(int &p) {
	int q=ls(p);
	ls(p)=rs(q), rs(q)=p, p=q;
	pushup(rs(p)), pushup(p);
}

void uprt(int &p) {
	int q=rs(p);
	rs(p)=ls(q), ls(q)=p, p=q;
	pushup(ls(p)), pushup(p);
}

void insert(int &p,int val) {
	if(p==0) {
		p=nnew(val);
		return;
	}
	if(val==v(p)) {
		c(p)++, pushup(p);
		return;
	}
	if(val<v(p)) {
		insert(ls(p),val);
		if(d(p)<d(ls(p))) uplt(p);
	}
	else {
		insert(rs(p),val);
		if(d(p)<d(rs(p))) uprt(p);
	}
	pushup(p);
}

int getpre(int val) {
	int ans=1, p=rt;
	for( ; p; p=val<v(p)?ls(p):rs(p)) {
		if(val==v(p)) {
			if(ls(p)) {
				for(p=ls(p); rs(p); p=rs(p));
				ans=p;
			}
			break;
		}
		if(v(p)<val&&v(p)>v(ans)) ans=p;
	}
	return v(ans);
}

int getnxt(int val) {
	int ans=2, p=rt;
	for( ; p; p=val<v(p)?ls(p):rs(p)) {
		if(v(p)==val) {
			if(rs(p)) {
				for(p=rs(p); ls(p); p=ls(p));
				ans=p;
			}
			break;
		}
		if(v(p)>val&&v(p)<v(ans)) ans=p;
	}
	return v(ans);
}

void remove(int &p,int val) {
	if(p==0) return;
	if(val==v(p)) {
		if(c(p)>1) {
			c(p)--, pushup(p);
			return;
		} 
		if(ls(p)||rs(p)) {
			if(rs(p)==0||d(ls(p))>d(rs(p)))
				uplt(p), remove(rs(p),val);
			else uprt(p), remove(ls(p),val);
			pushup(p); 
		}
		else p=0;
		return;
	}
	val<v(p)?remove(ls(p),val):remove(rs(p),val);
	pushup(p);
}

signed main() {
	srand((unsigned)time(0));
	build(); int n;
	scanf("%lld", &n);
	while(n--) {
		int op, x;
		scanf("%lld%lld", &op, &x);
		if(op==1) insert(rt,x);
		if(op==2) remove(rt,x);
		if(op==3) printf("%lld\n", getrk(rt,x)-1);
		if(op==4) printf("%lld\n", getval(rt,x+1));
		if(op==5) printf("%lld\n", getpre(x));
		if(op==6) printf("%lld\n", getnxt(x));
	}
	return 0;
} 

#define int long long
#define MN 101000 
const int INF=(int)1<<60;
struct treap {
	struct node {
		int ls, rs;
		int val, dat;
		int cnt, siz;
		#define ls(p) tr[p].ls
		#define rs(p) tr[p].rs
		#define v(p) tr[p].val
		#define d(p) tr[p].dat
		#define c(p) tr[p].cnt
		#define s(p) tr[p].siz
	} tr[MN]; 
	int top, rt;
	int nnew(int val) {
		v(++top)=val;
		d(top)=rand();
		c(top)=s(top)=1;
		return top;
	}
	void pushup(int p) {
		s(p)=s(ls(p))+s(rs(p))+c(p);
	}
	void build() {
		rt=nnew(-INF);
		rs(rt)=nnew(INF);
		pushup(rt);
	}
	int getrk(int p,int val) {
		if(p==0) return 0;
		if(val==v(p)) return s(ls(p))+1;
		if(val<v(p)) return getrk(ls(p),val);
		return getrk(rs(p),val)+s(ls(p))+c(p);
	}
	int getval(int p,int rk) {
		if(p==0) return INF;
		if(rk<=s(ls(p))) return getval(ls(p),rk);
		if(rk<=s(ls(p))+c(p)) return v(p);
		return getval(rs(p),rk-s(ls(p))-c(p)); 
	}
	void uplt(int &p) {
		int q=ls(p);
		ls(p)=rs(q), rs(q)=p, p=q;
		pushup(rs(p)), pushup(p);
	}
	void uprt(int &p) {
		int q=rs(p);
		rs(p)=ls(q), ls(q)=p, p=q;
		pushup(ls(p)), pushup(p);
	}
	void insert(int &p,int val) {
		if(p==0) {
			p=nnew(val);
			return;
		}
		if(val==v(p)) {
			c(p)++, pushup(p);
			return;
		}
		if(val<v(p)) {
			insert(ls(p),val);
			if(d(p)<d(ls(p))) uplt(p);
		}
		else {
			insert(rs(p),val);
			if(d(p)<d(rs(p))) uprt(p);
		}
		pushup(p);
	}
	int getpre(int val) {
		int ans=1, p=rt;
		for( ; p; p=val<v(p)?ls(p):rs(p)) {
			if(val==v(p)) {
				if(ls(p)) {
					for(p=ls(p); rs(p); p=rs(p));
					ans=p;
				}
				break;
			}
			if(v(p)<val&&v(p)>v(ans)) ans=p;
		}
		return v(ans);
	}
	int getnxt(int val) {
		int ans=2, p=rt;
		for( ; p; p=val<v(p)?ls(p):rs(p)) {
			if(v(p)==val) {
				if(rs(p)) {
					for(p=rs(p); ls(p); p=ls(p));
					ans=p;
				}
				break;
			}
			if(v(p)>val&&v(p)<v(ans)) ans=p;
		}
		return v(ans);
	}
	void remove(int &p,int val) {
		if(p==0) return;
		if(val==v(p)) {
			if(c(p)>1) {
				c(p)--, pushup(p);
				return;
			} 
			if(ls(p)||rs(p)) {
				if(rs(p)==0||d(ls(p))>d(rs(p)))
					uplt(p), remove(rs(p),val);
				else uprt(p), remove(ls(p),val);
				pushup(p); 
			}
			else p=0;
			return;
		}
		val<v(p)?remove(ls(p),val):remove(rs(p),val);
		pushup(p);
	}
} ;

标签：val,rs,int,tr,Treap,ls,define
From： https://www.cnblogs.com/chelsyqwq/p/17625750.html

相关文章

  • FHQ-Treap 详解
    目录1）FHQ-Treap基本功能理论与实现1.1）FHQ-Treap模型1.2）操作一：分裂（Split）1.3）操作二：合并（Merge）1.4）操作三：插入新节点1.5）删除某个节点1.6）查询某个值的排名1.7）查询排名为\(k\)的值1.8）查询\(x\)的前驱与后继1.9）Endofthisunit2）FHQ-Treap的应用2.1）洛谷P3369END1）FHQ-Treap基本功......
  • 『学习笔记』fhq-treap
    啥是平衡树这边建议去这里。分裂一般指的是按值分裂，意思就是以树上的BST（二叉搜索树）的值为关键值分裂。一般会给一个关键值\(val\)，把一棵平衡树分裂成BST值\(\leqval\)和\(>val\)的两部分。主要思想从根开始递归，递归到某一节点，如果当前根节点的BST值小于等于你给的那......
  • 无旋平衡树（范浩强Treap）平均时间复杂度证明
    范浩强Treap是一种应用广泛的数据结构（可参考OI_Wiki），然而网上难以找到比较严谨的复杂度证明.本文将严格证明\(n\)个结点的Treap的期望树高为\(\Theta(\logn)\)，由于一次分裂或合并操作的递归深度恰为树高，这便说明了一次操作的平均时间复杂度为\(\Theta(\logn)\).首先，由......
  • FHQ-Treap
    本文仅发布于此博客和作者的洛谷博客，不允许任何人以任何形式转载，无论是否标明出处及作者。前置废话fhq为什么是神。首先我们有一个正常Treap。正常Treap对于每一个值引入了一个随机的键，在节点的值形成一个BST的基础上，保证键形成一个小根堆。也就是把这一个BST做成了笛卡尔树......
  • 「学习笔记」FHQ-treap
    FHQ-treap，即无旋treap，又称分裂合并treap，支持维护序列，可持久化等特性。FHQ-treap有两个核心操作，分裂与合并。通过这两个操作，在很多情况下可以比旋转treap等方便的实现一些操作。FHQ-treap与其他的平衡树相比，他最明显的优点是：它好写！！！，想象一下，在考场上，你用较短的时间写出FH......
  • FHQ-Treap
    简介FHQ-Treap是一种无旋转的Treap。和大多数的平衡树不一样，它并不是用旋转来维护的，而是使用了split（分裂）和merge（合并）两种操作来维护Treap的性质。实现splitsplit操作可以将一个FHQ-Treap按照某个值分裂为两个FHQ-Treap：按照权值分：将权值\(\leval\)的放到一个......
  • FHQ-Treap的详细图解
    第一部分按值分裂的FHQ-Treap按值分裂的FHQ-Treap的典型例题是P3369【模板】普通平衡树。思路FHQ-Treap是什么？FHQ-Treap是二叉搜索树的一种。比如：FHQ-Treap的思想是什么？分裂->操作->合并下面我们就来慢慢讲这些操作。分裂我们可以根据给定的\(k\)将平衡树分......
  • 旋转Treap树
    #include<bits/stdc++.h>usingnamespacestd;constintM=1e6+10;intcnt=0;//cnt记录当前节点个数，最新一个节点即t[cnt]introot=0;//root是整棵树的树根，初始为空树所以root初始化=0intn;//n表示操作次数structNode{ intls,rs;//左右儿子 intval,pr......
  • 旋转Treap
    splay是通过splay操作均摊复杂度，而旋转treap也旋转，但是是通过随机赋权使得复杂度在期望下正确。具体来说就是再随机赋一个权值\(rank\)，通过旋转使得这棵树的\(val\)满足二叉搜索树且\(rank\)满足小根堆。具体来说，在查询的时候是不旋转的，只有在插入和删除时有旋转。......
  • 非旋TREAP
    非旋TREAP目录非旋TREAP一、TREAP—新的树形结构1.treap=tree+heap2.更优秀的时间复杂度3.treap的基础打法1.基本框架-开数组2.动态开点3.sz的维护4.分离和统一4.treap的进阶使用1.treap相比于线段树的好处2.在treap上pushup和pushdown1.总体规则1.在自己做了标记的事后下传标记，......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99