发表文章

[最新] Treap和FHQ式(无旋)Treap的模板(非指针)

wwwengine 1月前 0

测试例题:洛谷P3369。

Treap写得很好的非指针博客:

http://www.cnblogs.com/BCOI/p/9072444.html  写得好

http://www.cnblogs.com/HocRiser/p/8179557.html  也写得好

这个数据结构理解起来不难,稍微画一下图就可,结合注释容易理解。

注:此代码是随机权值小的优先级高。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>

using namespace std;

const int MAXN=100005;
const int INF=500000000;

int ch[MAXN][2];  //随机权值小的,优先级高 
int val[MAXN];    //当前节点的数字 
int size[MAXN];   //包括当前节点和左右子树的数字个数 
int cnt[MAXN];    //当前节点数字的个数 
int prior[MAXN];  //随机权值,保持堆的性质 
int rt=0, np=0;

void update(int now) { size[now] = size[ch[now][0]] + size[ch[now][1]] + cnt[now]; }  //更新 

void rotate(int &now, int dir)  //dir=0表示左旋,即逆时针旋转,右儿子成为根。以此为例 
{
	int son = ch[now][dir^1];  //右儿子 
	ch[now][dir^1] = ch[son][dir];  //右儿子的左儿子,变成now的右儿子 
	ch[son][dir] = now;  //右儿子的左儿子,现在是now 
	update(now); //一定先更新now,因为now已经是儿子了。 
	update(now = son);  //修改now 
}

void insert(int &now, int num)  //插入 
{
	if(!now)  //新建节点 
	{
		now = ++np;
		size[now] = cnt[now] = 1;
		prior[now] = rand();
		val[now] = num;
		return;
	}
	size[now]++;  //凡是经过,大小加一 
	if(val[now] == num) {cnt[now]++; return;}  //有现成的 
	int d = num > val[now];  //决定插入方向 
	insert(ch[now][d], num);
	if(prior[ch[now][d]] < prior[now]) rotate(now, d^1);  //如果不满足堆的性质了(此处是小根堆),旋转 
}

void remove(int &now, int num)  //删除 
{
	if(!now) return;  //边界(即没有这个元素) 
	if(val[now] == num)  //找到 
	{
		if(cnt[now] > 1) {size[now]--; cnt[now]--; return;}  //有现成的,且重复出现过 
		if(!ch[now][0] || !ch[now][1]) {now = ch[now][0] + ch[now][1]; return;} //说明只出现了1次,如果有空子树,拿非空的来代替它就行了 
		int d = prior[ch[now][1]] < prior[ch[now][0]]; //如果两棵子树都有,那么取随机权值小的旋成根 
		rotate(now, d^1); remove(now, num);  //不断把now旋转到成为叶子结点,然后回归到上面两种情况 
		return;
	}
	
	size[now]--;  //凡是经过,减一 
	int d = num > val[now];  //决定删除方向 
	remove(ch[now][d], num);
}

int rank(int now, int num)  //查找排名 
{
	if(!now) return 0;  //边界 
	if(num == val[now]) return size[ch[now][0]] + 1;  // 刚好找到 
	int d = num > val[now];  //决定查找方向 
	if(d) return size[ch[now][0]] + cnt[now] + rank(ch[now][1], num);  //如果数字很大,往右找,左边的一并算上 
	return rank(ch[now][0], num);  //数字小,往左找 
}

int kth(int now, int k)  //查排名从小到大第k的元素 
{
	while(now)
	{
		if(k <= size[ch[now][0]]) now = ch[now][0]; 
		else if(k > size[ch[now][0]] + cnt[now]) k -= size[ch[now][0]] + cnt[now], now = ch[now][1];
		else return val[now]; //如果不比左子树小,又不比左子树和当前节点之和大,说明介于两者之间,即就是当前节点的值 
	}
}

int pre(int now, int num)  //第一个小于num的数 
{
	if(!now) return -INF; //不影响答案 
	if(num <= val[now]) return pre(ch[now][0], num);  //注意,这个等号必须加 
	return max(val[now], pre(ch[now][1], num)); //有可能右子树找不到,所以要考虑当前节点 
}

int next(int now, int num)  //第一个大于num的数 
{
	if(!now) return INF;
	if(num >= val[now]) return next(ch[now][1], num); //注意,这个等号必须加 
	return min(val[now], next(ch[now][0], num));  //同上,有可能左子树找不到 
}

int main()
{
	int N,op,x; scanf("%d",&N);
	
	while(N--)
	{
		scanf("%d%d",&op,&x);
		if(op == 1) insert(rt, x);
		else if(op == 2) remove(rt, x);
		else if(op == 3) printf("%d\n", rank(rt, x));
		else if(op == 4) printf("%d\n", kth(rt, x));
		else if(op == 5) printf("%d\n", pre(rt, x));
		else printf("%d\n", next(rt, x));
	}
	
	return 0;
}

 

FHQ式(无旋)Treap:

例题:洛谷: 普通平衡树,文艺平衡树

代码很不错,解析也很好的博客:http://blog.csdn.net/CABI_ZGX/article/details/79963427

讲解上面的博客很好,下面的代码就是从上面搬的,可以仔细看一下。

补一句,虽然它的很多操作我还不会,但它的确可以做到很多数据结构的工作,比如Splay,SBT等等,并且下面可以看到核心的几行编写还是很简单。这种数据结构很值得一学!

 

普通平衡树:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdlib>

using namespace std;

const int MAXN = 100005;
const int INF = 500000000;

int val[MAXN];  // 小的排左子树,大的右子树 
int ch[MAXN][2];  
int size[MAXN];   //自己以及左右子树的大小 
int prior[MAXN];  //随机权值小的 优先级高
int root=0,np=0;

void update(int now) { size[now] = size[ch[now][0]] + size[ch[now][1]] + 1; }  

int new_node(int num)
{
	np++;
	size[np] = 1;
	val[np] = num;
	prior[np] = rand();
	return np;
}

int merge(int x, int y)  //合并编号为x,y的树。默认y>x 
{
	if(!x || !y) return x + y;  //如果有一个是0,返回另一个 
	if(prior[x] < prior[y])  //随机权值小的放上面。 
	{
		ch[x][1] = merge(ch[x][1], y);
		update(x); return x;
	}
	else
	{
		ch[y][0] = merge(x,ch[y][0]);
		update(y); return y;
	} //记得更新 
}

void split(int now, int num, int &x, int &y)//把以now为根的树分为x,y两棵 
{
	if(!now) x = y = 0;  //now自己是空的,子树也是空的 
	else
	{
		if(val[now] <= num) x = now, split(ch[now][1], num, ch[now][1], y); // num大了,往右走,同时x也就确定了 
		else y = now, split(ch[now][0], num, x, ch[now][0]);  
		update(now);//记得更新 
	}
}

int kth(int now, int k)
{
	while(1)
	{
		if(k <= size[ch[now][0]]) now = ch[now][0]; //如果k小了,往左找 
		else if(k > size[ch[now][0]] + 1) k -= size[ch[now][0]] + 1, now = ch[now][1]; //k大了,往右找 
		else return now; //恰好,返回 
	}
}
int main()
{
	int N, op, num, x, y, z; scanf("%d", &N);
	
	while(N--)
	{
		scanf("%d%d", &op, &num);
		if(op == 1)
		{
			split(root, num, x, y); 
			root = merge( merge(x, new_node(num)), y );
		}
		
		else if(op == 2)
		{
			split(root, num, x, z);
			split(x, num-1, x, y);
			y = merge(ch[y][0], ch[y][1]);
			root = merge( merge(x, y), z );
		}
		
		else if(op == 3)
		{
			split(root, num-1, x, y);
			printf("%d\n", size[x] + 1);
			root = merge(x, y);
		}
		
		else if(op == 4) printf("%d\n", val[kth(root, num)]);
		
		else if(op == 5)
		{
			split(root, num-1, x, y);
			printf("%d\n", val[kth(x, size[x])]);
			root = merge(x, y);
		}
		
		else
		{
			split(root, num, x, y);
			printf("%d\n", val[kth(y, 1)]);
			root = merge(x, y);
		}
	}
	
	return 0;
}

 

文艺平衡树:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;

const int MAXN=100005;

int val[MAXN];  //节点代表的下标 
int ch[MAXN][2];  
int size[MAXN];  //自己及左右子树的大小 
int prior[MAXN]; //随机权值 
int inver[MAXN];  //旋转标记 
int np=0,root=0,N,M;

void update(int now)
{
	size[now] = size[ch[now][1]] + size[ch[now][0]] + 1;
	if(now && inver[now]) //如果打上了旋转标记 
	{
		swap(ch[now][0], ch[now][1]);  //旋转左右子树 
		inver[ch[now][0]] ^= 1;  //下传标记 
		inver[ch[now][1]] ^= 1;  
		inver[now] ^= 1;  //下传完毕,改回来 
	}
}

int new_node(int num)
{
	np++;
	size[np] = 1;
	val[np] = num;
	prior[np] = rand();
	return np;
}

int build(int l, int r)
{
	if(l>r) return 0;
	int mid = (l+r)/2, v = mid-1;
	int now = new_node(v);  // 这个区间的中间值作为权值 
	ch[now][0] = build(l,mid-1);  
	ch[now][1] = build(mid+1,r);
	update(now); return now;  //记得更新 
}

int merge(int x,int y)
{
	if(!x || !y) return x+y;
	update(x); update(y);  // 先更新,因为要分开了 
	if(prior[x] < prior[y])
	{
		ch[x][1] = merge(ch[x][1], y);
		update(x); return x;
	}
	else
	{
		ch[y][0] = merge(x, ch[y][0]);
		update(y); return y;
	}
}

void split(int now, int num, int &x, int &y)
{
	if(!now) x = y = 0;
	else
	{
		update(now);
		if(num <= size[ch[now][0]]) {y = now; split(ch[now][0], num, x, ch[now][0]);}
		else {x = now; split(ch[now][1], num - size[ch[now][0]] - 1, ch[now][1], y);}
		update(now);
	}
}

void rev(int l, int r)
{
	int a, b, c, d;  //
	split(root, r+1, a, b);//先把树分成 a树:1~r;然后再把a树分成c树:1~l-1,d树:l~r 
	split(a, l, c, d);
	inver[d] ^= 1;  //d树:l~r 
	root = merge(merge(c, d), b);
}

int kth(int now, int k)
{
	while(1)
	{
		if(k <= size[ch[now][0]]) now = ch[now][0];
		else if(k > size[ch[now][0]] + 1) k -= size[ch[now][0]] + 1, now = ch[now][1];
		else return now;
	}
}

void print(int now)
{
	if(!now) return;
	update(now);
	print(ch[now][0]);
	if(val[now] >= 1 && val[now] <= N) printf("%d ",val[now]); //因为建树时边界设得大一点点,所以这里要判断是否过大 
	print(ch[now][1]);
}

int main()
{
	int l, r; scanf("%d%d",&N, &M);

	root = build(1, N+2);

	while(M--)
	{
		scanf("%d%d",&l, &r);
		rev(l, r);
	}
	
	print(root);
	
	return 0;
}

 

相关推荐
最新评论 (0)
返回
发表文章
wwwengine
文章数
99
评论数
0
注册排名
1312508