关于旋转treap平衡树
  • 板块学术版
  • 楼主operator_
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/2/26 17:06
  • 上次更新2023/10/23 23:40:41
查看原帖
关于旋转treap平衡树
499682
operator_楼主2023/2/26 17:06

如果要把treap的优先级调整,要改哪里,每个函数都要改吗?(比如把最小优先改为最大优先)以下是对着模板打的

struct treap {
	int l[100005],r[100005],v[100005],rnk[100005],s[100005],w[100005],sz,ans,rt;
	void pushup(int x) {s[x]=s[l[x]]+s[r[x]]+w[x];}
	void lrotate(int &k) {
		int t=r[k];
		r[k]=l[t],l[t]=k,s[t]=s[k],pushup(k),k=t;
	}
	void rrotate(int &k) {
		int t=l[k];
		l[k]=r[t],r[t]=k,s[t]=s[k],pushup(k),k=t;
	}
	void insert(int &k,int x) {//单点插入 
		if(!k) {
			k=++sz,s[k]=1,w[k]=1,v[k]=x,rnk[k]=rand();
			return;
		}
		s[k]++;
		if(v[k]==x) w[k]++;
		if(v[k]<x) {
			insert(r[k],x);
			if(rnk[r[k]]<rnk[k]) lrotate(k);
		} 
		if(v[k]>x) {
			insert(l[k],x);
		    if(rnk[l[k]]<rnk[k]) rrotate(k);
        }
	}
	bool del(int &k,int x) {//单点删除 
		if(!k) return false;
		if(v[k]==x) {
			if(w[k]>1) {w[k]--,s[k]--;return true;}
			if(l[k]==0||r[k]==0) {k=l[k]+r[k];return true;} 
			else if(rnk[l[k]]<rnk[r[k]]) {rrotate(k);return del(k,x);} 
			else {lrotate(k);return del(k,x);}
		} 
		else if(v[k]<x) {
			bool succ=del(r[k],x);
			if(succ) s[k]--;return succ;
		} 
		else {
			bool succ=del(l[k],x);
			if(succ) s[k]--;return succ;
		}
	}
	int queryrank(int k,int x) {//单点查询排名 
		if(!k) return 0;
		if(v[k]==x) return s[l[k]]+1;
		else if(x>v[k]) return s[l[k]]+w[k]+queryrank(r[k],x);
		else return queryrank(l[k],x);
	}
	int querynum(int k,int x) {//单点查询数值 
		if(!k) return 0;
		if(x<=s[l[k]]) return querynum(l[k],x);
		else if(x>s[l[k]]+w[k]) return querynum(r[k],x-s[l[k]]-w[k]);
		else return v[k];
	}
	void queryp(int k,int x) {
		if(!k) return;
		if(v[k]<x) ans=k,queryp(r[k],x);
		else queryp(l[k],x);
	}
	int querypre(int k,int x) {//单点查询前驱 
		ans=0;
		queryp(k,x);
		if(!ans) return -1;
		else return v[ans];
	}
	void querys(int k,int x) {
		if(!k) return;
		if(v[k]>x) ans=k,querys(l[k],x);
		else querys(r[k],x);
	}
	int querysub(int k,int x) {//单点查询后继
		ans=0;
		querys(k,x);
		if(!ans) return -1;
		else return v[ans];
	}
}t;
2023/2/26 17:06
加载中...