非旋Treap模板

  • 2018-03-03
  • 0
  • 0

传统的旋转 Treap 是一棵名次树,只能处理名次相关的询问。

那么如果碰到区间问题,难道只能打 Splay 了吗?非也!

Treap 的非旋版本不但可以较快地处理名次问题,还能一样快地处理区间问题!

既然是“非旋”,我们就不能用 rotate 操作来维护平衡了,而是引入了两个神奇的函数:

  • split(u, pos),将以 u 为根节点的 Treap 在第 pos 个元素后分裂,并返回分裂出来的两个根
  • merge(u, v),将元素相对有序的两棵 Treap 合并为一棵,维护堆性质,并返回合并后的根。

两个函数的具体实现详见代码 (%%% zcysky dalao)

至于各操作,我们发现询问名次询问第 k 小以及询问前驱/后继都不会改变树的结构,可直接利用二叉排序树的性质 O(logn) 解决。

插入/删除操作则会改变树的结构,需要用 split 和 merge 实现并维护:

  • insert = split + merge + merge ⇒ O(logn)
  • erase = split + split + merge ⇒ O(logn)

这样就能够完美地处理名次问题了,虽然常数较传统 Treap 略大

而利用 split 和 merge 操作,可以 O(logn) 将区间分离出来,进行区间处理。

  • Any interval = split + split + merge + merge ⇒ O(logn)

避免了 rotate 操作,树的结构保持稳定,还可以进行可持久化。这些都是非旋 Treap 的优势。

至于模板题,还是熟悉的 BZOJ 3224 普通平衡树以及 BZOJ 3223 文艺平衡树,题目就不再贴出了。

BZOJ 3224 Code: O(nlogn) [3252K, 468MS]

// 无旋 Treap (2018.3.3)
// BZOJ 3224 普通平衡树 
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 100005
#define INFINT 0x3f3f3f3f
using namespace std;
typedef pair<int, int> PII;

inline void getint(int &num){
	char ch; bool neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
	if(neg) num = -num;
}

int n, opt, x;

struct Treap{
	int root, val[MAXN], wt[MAXN], size[MAXN], lc[MAXN], rc[MAXN], topp;
	
	inline void update(int u) {size[u] = size[lc[u]] + size[rc[u]] + 1;}
	
	inline PII split(int u, int pos){
		if(!pos) return make_pair(0, u);
		int l = lc[u], r = rc[u];
		if(pos == size[l]) return lc[u] = 0, update(u), make_pair(l, u);  // Exactly cut off whole left subtree
		else if(pos == size[l] + 1) return rc[u] = 0, update(u), make_pair(u, r);  // Exactly cut off whole right subtree
		else if(pos < size[l]){
			PII roots = split(l, pos);
			return lc[u] = roots.second, update(u), make_pair(roots.first, u);
		}
		else{
			PII roots = split(r, pos - size[l] - 1);
			return rc[u] = roots.first, update(u), make_pair(u, roots.second);
		}
	}
	
	inline int merge(int u, int v){
		if(!u || !v) return u | v;
		if(wt[u] < wt[v]) return rc[u] = merge(rc[u], v), update(u), u;
		else return lc[v] = merge(u, lc[v]), update(v), v;
	}
	
	inline int rnk(int x){
		int u = root, delta = 0, res = INFINT;
		while(u){
			if(x == val[u]) res = min(res, delta + size[lc[u]] + 1);
			if(x > val[u]) delta += size[lc[u]] + 1, u = rc[u];
			else u = lc[u];
		}
		return res < INFINT ? res : delta + 1;
	}
	
	inline int kth(int k){
		int u = root;
		while(u){
			if(size[lc[u]] + 1 == k) return val[u];
			if(size[lc[u]] + 1 > k) u = lc[u];
			else k -= size[lc[u]] + 1, u = rc[u];
		}
	}
	
	inline int pred(int x){
		int u = root, res = -INFINT;
		while(u){
			if(val[u] < x) res = max(res, val[u]), u = rc[u];
			else u = lc[u];
		}
		return res;
	}
	
	inline int succ(int x){
		int u = root, res = INFINT;
		while(u){
			if(val[u] > x) res = min(res, val[u]), u = lc[u];
			else u = rc[u];
		}
		return res;
	}
	
	inline void insert(int x){
		int k = rnk(x + 1) - 1; PII roots = split(root, k);
		val[++topp] = x, wt[topp] = rand(), size[topp] = 1;
		root = merge(merge(roots.first, topp), roots.second);
	}
	
	inline void erase(int x){
		int k = rnk(x); PII rootr = split(root, k), rootl = split(rootr.first, k - 1);
		root = merge(rootl.first, rootr.second);
	}
} treap;

int main(){
	srand(19260817), getint(n);
	for(register int i = 1; i <= n; i++){
		getint(opt), getint(x);
		if(opt == 1) treap.insert(x);
		else if(opt == 2) treap.erase(x);
		else if(opt == 3) printf("%d\n", treap.rnk(x));
		else if(opt == 4) printf("%d\n", treap.kth(x));
		else if(opt == 5) printf("%d\n", treap.pred(x));
		else if(opt == 6) printf("%d\n", treap.succ(x));
	}
	return 0;
}

BZOJ 3223 Code: O(nlogn) [3744K, 2600MS]

// 无旋 Treap 区间反转 (2018.3.4)
// BZOJ 3223 文艺平衡树
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 100005
using namespace std;
typedef pair<int, int> PII;

inline void getint(int &num){
	char ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int n, m, l, r;

struct Treap{
	int root, val[MAXN], wt[MAXN], size[MAXN], lc[MAXN], rc[MAXN], topp;
	bool rev[MAXN];
	
	inline void update(int u) {size[u] = size[lc[u]] + size[rc[u]] + 1;}
	
	inline void pushdown(int u){
		if(rev[u]){
			swap(lc[u], rc[u]);
			rev[lc[u]] ^= 1, rev[rc[u]] ^= 1;
			rev[u] = 0;
		}
	}
	
	inline PII split(int u, int pos){
		pushdown(u);
		if(!pos) return make_pair(0, u);
		int l = lc[u], r = rc[u];
		if(pos == size[l]) return lc[u] = 0, update(u), make_pair(l, u);
		else if(pos == size[l] + 1) return rc[u] = 0, update(u), make_pair(u, r);
		else if(pos < size[l]){
			PII roots = split(l, pos);
			return lc[u] = roots.second, update(u), make_pair(roots.first, u);
		}
		else{
			PII roots = split(r, pos - size[l] - 1);
			return rc[u] = roots.first, update(u), make_pair(u, roots.second);
		}
	}
	
	inline int merge(int u, int v){
		if(!u || !v) return pushdown(u | v), u | v;
		if(wt[u] < wt[v]) return pushdown(u), rc[u] = merge(rc[u], v), update(u), u;
		else return pushdown(v), lc[v] = merge(u, lc[v]), update(v), v;
	}
	
	inline void build(int n){
		int *stk = new int[MAXN], tops = 0; stk[0] = 0, topp = n;
		for(register int i = 1; i <= n; i++) val[i] = i, wt[i] = rand(), size[i] = 1, lc[i] = rc[i] = 0, rev[i] = 0;
		for(register int i = 1; i <= n; i++){
			int o = 0;
			while(tops && wt[i] < wt[stk[tops]]) update(o = stk[tops--]);
			rc[stk[tops]] = i, lc[i] = o;
			stk[++tops] = i;
		}
		while(tops) update(stk[tops--]);
		root = stk[1];
		delete []stk;
	}
	
	inline void reverse(int l, int r){
		PII rootr = split(root, r), rootl = split(rootr.first, l - 1);
		rev[rootl.second] ^= 1;
		root = merge(merge(rootl.first, rootl.second), rootr.second);
	}
	
	inline void inorder(int u){
		pushdown(u);
		if(lc[u]) inorder(lc[u]);
		printf("%d ", val[u]);
		if(rc[u]) inorder(rc[u]);
	}
} treap;

int main(){
	getint(n), getint(m);
	treap.build(n);
	for(register int i = 1; i <= m; i++){
		getint(l), getint(r);
		treap.reverse(l, r);
	}
	treap.inorder(treap.root), puts("");
	return 0;
}

由于频繁调用 cstdlib 中的 rand() 效率较低,我们可以自己实现伪随机数生成器,例如:

typedef unsigned int uint;

inline uint RAND(){
	static uint _seed = 643;
	return _seed = _seed * 48271;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai