旋转Treap/Splay模板

  • 2018-02-17
  • 0
  • 1

这两天又种了两棵平衡树，分别是 Treap 和 Splay。

【旋转 Treap】

模板题：BZOJ 3224

Treap = Tree + Heap，中文名叫树堆，是一种基于随机化的二叉排序树。

普通的二叉排序树在递增或递减的输入下会退化成为一条链，最坏复杂度达 O(n)。

所以我们给每个节点额外赋一个随机值，保持该值满足堆的性质。

就可以达到单次期望 O(logn) 的效果，且不易退化。

旋转 Treap 的思想就是用不破坏中序遍历的旋转操作来维护堆的性质。

注意，为了处理方便，我们将相同的值储存在同一节点内，记录个数即可。

常数似乎较宗法树更大一些。

Code: O(nlogn) [5980K, 532MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100002;

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 Node{
	#define sz(x) ((x) ? (x)->size : 0)
	int val, pri, cnt, size;
	Node *lc, *rc;
	
	Node() {}
	Node(int v, int c, int s, Node *l, Node *r): val(v), cnt(c), size(s), lc(l), rc(r) {}
	
	inline void update() {size = sz(lc) + sz(rc) + cnt;}
} pool[MAXN << 1];

inline Node* newNode(int v, int c, int s, Node *l, Node *r){
	static int topp = 0;
	pool[topp] = Node(v, c, s, l, r);
	return &pool[topp++];
}

inline void rotate(Node *&cur, int dir){
	if(dir == 0){
		Node *o = cur->lc; cur->lc = o->rc, o->rc = cur;
		o->size = cur->size, cur->update(), cur = o;
	}
	else{
		Node *o = cur->rc; cur->rc = o->lc, o->lc = cur;
		o->size = cur->size, cur->update(), cur = o;
	}
}

inline void insert(Node *&cur, int v){
	if(cur == NULL) cur = newNode(v, 1, 1, NULL, NULL);
	else{
		cur->size++;
		if(v == cur->val) cur->cnt++;
		else if(v > cur->val){
			insert(cur->rc, v);
			if(cur->rc->pri < cur->pri) rotate(cur, 1);
		}
		else{
			insert(cur->lc, v);
			if(cur->lc->pri < cur->pri) rotate(cur, 0);
		}
	}
}

inline void erase(Node *&cur, int v){
	if(cur == NULL) return;
	if(v == cur->val){
		if(cur->cnt > 1) cur->cnt--, cur->size--;
		else{
			if(cur->lc && cur->rc){
				if(cur->lc->pri < cur->rc->pri) rotate(cur, 0), erase(cur, v);
				else rotate(cur, 1), erase(cur, v);  // 直接 "erase(cur->lc, v)" 会导致 size 没有更新 !!! 
			}
			else cur = cur->lc ? cur->lc : cur->rc;
		}
	}
	else{
		cur->size--;
		if(v > cur->val) erase(cur->rc, v);
		else erase(cur->lc, v);
	}
}

inline int rnk(Node *cur, int v){
	if(cur == NULL) return 1;  // 类比 "宗法树" 的 "return 2;" 操作 
	if(v == cur->val) return sz(cur->lc) + 1;
	else if(v < cur->val) return rnk(cur->lc, v);
	else return sz(cur->lc) + cur->cnt + rnk(cur->rc, v);
}

inline int kth(Node *cur, int k){
	if(cur == NULL) return 0;
	if(k <= sz(cur->lc)) return kth(cur->lc, k);
	else if(k > sz(cur->lc) + cur->cnt) return kth(cur->rc, k - sz(cur->lc) - cur->cnt);
	else return cur->val;
}

int main(){
	srand(19260817);
	getint(n);
	Node *root = NULL;
	while(n--){
		getint(opt), getint(x);
		if(opt == 1) insert(root, x);
		else if(opt == 2) erase(root, x);
		else if(opt == 3) printf("%d\n", rnk(root, x));
		else if(opt == 4) printf("%d\n", kth(root, x));
		else if(opt == 5) printf("%d\n", kth(root, rnk(root, x) - 1));
		else if(opt == 6) printf("%d\n", kth(root, rnk(root, x + 1)));
	}
	return 0;
}

【Splay】Wikipedia

模板题：BZOJ 3223

Splay 中文名叫伸展树，是一种二叉排序树。

它是处理区间问题的利器，但是相对来说常数比较大。

若将 l - 1 旋转至根节点，r + 1 旋转至根的右节点，那么 r + 1 的左子树即为区间 [l, r]。

Code: O(nlogn) [11064K, 1820MS]

// Splay Tree (Balanced Binary Search Tree)
// BZOJ 3223 文艺平衡树 
/*
	rotate(cur, dir):
		右旋(dir == 0): 设 cur 的左孩子为 o
			(1) 将 o 的右子树连在 cur 的左子树上 
			(2) 将 o 连在 cur 的父亲的左/右子树上 
			(3) 将 cur 连在 o 的右子树上 
		左旋(dir == 1): 设 cur 的右孩子为 o 
			(1) 将 o 的左子树连在 cur 的右子树上 
			(2) 将 o 连在 cur 的父亲的左/右子树上 
			(3) 将 cur 连在 o 的左子树上 
	splay(cur, tf):
		Zig Step: 当 cur 的父节点离目标父节点 tf 只差一层时, 旋转父节点 
		Zig-zig Step: 若 cur 与其父节点子树情况相同, 先旋转爷爷节点, 再旋转父节点 
		Zig-zag Step: 若 cur 与其父节点子树情况相反, 旋转父节点不同方向各一次 
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100002;

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, a[MAXN];

struct Splay_Tree{
	struct Node{
		#define islc(cur) ((cur) == (cur)->fa->ch[0])
		#define isrc(cur) ((cur) == (cur)->fa->ch[1])
		int val, size, rev;
		Node *fa, *ch[2];
		
		Node(): val(0), size(0), rev(0), fa(NULL) {ch[0] = ch[1] = NULL;}
		Node(int v, int s, Node *f, Node *l, Node *r): val(v), size(s), rev(0), fa(f) {ch[0] = l, ch[1] = r;}
		
		inline void update() {size = (ch[0] ? ch[0]->size : 0) + (ch[1] ? ch[1]->size : 0) + 1;}
		
		inline void pushdown(){
			if(rev){
				swap(ch[0], ch[1]);
				if(ch[0]) ch[0]->rev ^= 1;
				if(ch[1]) ch[1]->rev ^= 1;
				rev = 0;
			}
		}
	} pool[MAXN << 2], *root;
	
	inline Node* newNode(int v, int s, Node *f, Node *l, Node *r){
		static int topp = 0;
		pool[topp] = Node(v, s, f, l, r);
		return &pool[topp++];
	}
	
	inline Node* build(int *sorted, int l, int r, Node *fa = NULL){
		int smid = l + r >> 1;
		Node *cur = newNode(sorted[smid], 0, fa, NULL, NULL);
		if(l < smid) cur->ch[0] = build(sorted, l, smid - 1, cur);
		if(smid < r) cur->ch[1] = build(sorted, smid + 1, r, cur);
		return cur->update(), cur;
	}
	
	inline void rotate(Node *cur, int dir){
		Node *o = cur->ch[dir];
		if(!o) return;
		cur->pushdown(), o->pushdown();
		
		cur->ch[dir] = o->ch[dir ^ 1];
		if(o->ch[dir ^ 1]) o->ch[dir ^ 1]->fa = cur;
		
		o->fa = cur->fa;
		if(!cur->fa) root = o;
		else if(islc(cur)) cur->fa->ch[0] = o;
		else cur->fa->ch[1] = o;
		
		o->ch[dir ^ 1] = cur, cur->fa = o;
		cur->update(), o->update();
	}
	
	inline void splay(Node *cur, Node *tf){
		while(cur->fa != tf){
			if(cur->fa->fa == tf) if(islc(cur)) rotate(cur->fa, 0); else rotate(cur->fa, 1);
			else if(islc(cur) && islc(cur->fa)) rotate(cur->fa->fa, 0), rotate(cur->fa, 0);
			else if(isrc(cur) && isrc(cur->fa)) rotate(cur->fa->fa, 1), rotate(cur->fa, 1);
			else if(islc(cur) && isrc(cur->fa)) rotate(cur->fa, 0), rotate(cur->fa, 1);
			else rotate(cur->fa, 1), rotate(cur->fa, 0);
		}
	}
	
	inline Node* find(int id){
		Node *p = root;
		while(p){
			p->pushdown();
			int lsize = p->ch[0] ? p->ch[0]->size + 1 : 1;
			if(id < lsize) p = p->ch[0];
			else if(id > lsize) id -= lsize, p = p->ch[1];
			else return p;
		}
		return NULL;
	}
	
	inline void reverse(int l, int r){
		if(l >= r) return;
		Node *pl = find(l - 1), *pr = find(r + 1);
		if(pl && pr) {splay(pl, NULL), splay(pr, pl); if(pr->ch[0]) pr->ch[0]->rev ^= 1;}
		else if(pr) {splay(pr, NULL); if(pr->ch[0]) pr->ch[0]->rev ^= 1;}
		else if(pl) {splay(pl, NULL); if(pl->ch[1]) pl->ch[1]->rev ^= 1;}
		else if(root) root->rev ^= 1;
	}
	
	inline void inorder(Node *cur){
		cur->pushdown();
		if(cur->ch[0]) inorder(cur->ch[0]);
		printf("%d ", cur->val);
		if(cur->ch[1]) inorder(cur->ch[1]);
	}
} splay;

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

评论

  • bjz回复

    种树巨爷%%%%%%%%%



常年不在线的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