宗法树模板

今天种了一棵平衡树，名字已~~不可考~~，有可能类似于 Finger Tree 或是 Leafy Tree。

至于中文名。。是 lxl 大佬的叫法（QAQ 实际上是 Drench 说的？？？不要依此考据啊啊……我还是太菜了 QAQ），来源于 Line 84~85 删数时神似 “父死子继” “长兄为父”。

其本质是一棵带旋转操作的名次树。

每个节点有四个属性：val (子树 val 最大值), size (子树大小), lc (左儿子指针), rc (右儿子指针)。

其中 val 只有叶子节点处为真实值，其余的只是左右子树 val 中的较大值。

宗法树满足二叉排序树性质和线段树部分性质，据说可以基本替代 Treap/Splay，还容易理解。

目前 lxl 大佬认为唯一不易替代的是 Splay 维护 LCT 的功能。~~（虽然我 LCT 都不会写）~~

有一道叫做 “普通平衡树（Treap/SBT）” 的模板题，各大 OJ 上应该都有 (BZOJ 3224)。

Problem:

Time Limit: 10 Sec Memory Limit: 128 MB

Description

您需要写一种数据结构(可参考题目标题)，来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，应只删除一个)
3. 查询x数的排名(若有多个相同的数，应输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

Input

第一行为n，表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)

Output

对于操作3,4,5,6每行输出一个数，表示对应答案

Sample Input

Sample Output

106465
84185
492737

HINT

1. n的数据范围：n<=100000

2. 每个数的数据范围：[-2e9,2e9]

Code: O(nlogn) [7548K, 364MS]

// 宗法树 (Balanced Tree)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100002;
const int ratio = 4;

template<typename T>
inline void getint(T &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{
	int val, size;
	Node *lc, *rc;
	
	Node(): val(0), size(0), lc(NULL), rc(NULL) {}
	Node(int v, int s, Node *l, Node *r): val(v), size(s), lc(l), rc(r) {}
	
	inline bool isleaf() {return lc == NULL;}
	
	inline void pushup(){
		if(isleaf()) return;
		size = lc->size + rc->size;
		val = max(lc->val, rc->val);
	}
} pool[MAXN << 2];

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

inline void rotate(Node *cur, int dir){
	if(dir == 0){  // Rightward rotate
		Node *r = cur->rc;
		cur->rc = cur->lc, cur->lc = cur->rc->lc;
		cur->rc->lc = cur->rc->rc, cur->rc->rc = r;
		cur->rc->pushup();
	}
	else{  // Leftward rotate
		Node *l = cur->lc;
		cur->lc = cur->rc, cur->rc = cur->lc->rc;
		cur->lc->rc = cur->lc->lc, cur->lc->lc = l;
		cur->lc->pushup();
	}
}

inline void maintain(Node *cur){
	if(cur->isleaf()) return;
	if(cur->lc->size > cur->rc->size * ratio) rotate(cur, 0);
	if(cur->rc->size > cur->lc->size * ratio) rotate(cur, 1);
}

inline void insert(Node *&cur, int v){
	if(cur == NULL) cur = newNode(v, 1, NULL, NULL);
	else{
		if(cur->isleaf()){
			cur->lc = newNode(min(v, cur->val), 1, NULL, NULL);
			cur->rc = newNode(max(v, cur->val), 1, NULL, NULL);
		}
		else{
			if(v > cur->lc->val) insert(cur->rc, v);
			else insert(cur->lc, v);
		}
		cur->pushup();
		maintain(cur);
	}
}

inline void erase(Node *cur, Node *fa, int v){
	if(cur->isleaf()){
		if(cur == fa->lc) *fa = *fa->rc;
		else *fa = *fa->lc;
	}
	else{
		if(v > cur->lc->val) erase(cur->rc, cur, v);
		else erase(cur->lc, cur, v);
		cur->pushup();
		maintain(cur);
	}
}

inline int rnk(Node *cur, int v){
	if(cur->isleaf()){
		if(v > cur->val) return 2;
		return 1;
	}
	else{
		if(v > cur->lc->val) return rnk(cur->rc, v) + cur->lc->size;
		else return rnk(cur->lc, v);
	}
}

inline int kth(Node *cur, int k){
	if(cur->isleaf()) return cur->val;
	else{
		if(k > cur->lc->size) return kth(cur->rc, k - cur->lc->size);
		else return kth(cur->lc, k);
	}
}

int main(){
	getint(n);
	Node *root = NULL;
	while(n--){
		getint(opt), getint(x);
		if(opt == 1) insert(root, x);
		else if(opt == 2) erase(root, 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;
}

Optimized Code: O(nlogn) [70344K, 200MS]

加入了飞快的读入/输出优化，并对递归部分进行循环展开。

// lxl & ddd 宗法树 (Balanced Tree)
// BZOJ 3224 普通平衡树 
/*
	每个节点要么没有子树, 要么有 2 个子树 
	叶节点保存值, 非叶节点保存 2 个子树值的较大值 
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100002;
const int ratio = 4;

struct file_io{
	#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')
	char inbuf[1 << 25], *pin, outbuf[1 << 25], *pout;
	int stk[20];
	
	file_io(): pout(outbuf) {fread(pin = inbuf, 1, 1 << 25, stdin);}
	~file_io() {fwrite(outbuf, 1, pout - outbuf, stdout);}
	
	inline void getint(int &num){
		bool neg = 0; num = 0;
		while(!isdigit(*pin)) if(*pin++ == '-') neg = 1;
		while(isdigit(*pin)) num = num * 10 + *pin++ - '0';
		if(neg) num = -num;
	}
	
	inline void putint(int num){
		static int *v = stk;
		if(!num) *pout++ = '0';
		else{
			if(num < 0) *pout++ = '-', num = -num;
			for(; num; num /= 10) *v++ = num % 10;
			while(v != stk) *pout++ = *--v + '0';
		}
	}
	
	inline void nextline() {*pout++ = '\n';}
} fio;
#define getint(num) fio.getint(num)
#define putint(num) fio.putint(num)
#define nextline() fio.nextline()

int n, opt, x;

struct Node{
	int val, size;
	Node *lc, *rc;
	
	Node(): val(0), size(0), lc(NULL), rc(NULL) {}
	Node(int v, int s, Node *l, Node *r): val(v), size(s), lc(l), rc(r) {}
	
	inline bool isleaf() {return lc == NULL;}
	
	inline void update(){
		if(isleaf()) return;
		size = lc->size + rc->size;
		val = max(lc->val, rc->val);
	}
} pool[MAXN << 1];

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

inline void rotate(Node *cur, int dir){
	if(dir == 0){  // Rightward rotate
		Node *r = cur->rc;
		cur->rc = cur->lc, cur->lc = cur->rc->lc;
		cur->rc->lc = cur->rc->rc, cur->rc->rc = r;
		cur->rc->update();
	}
	else{  // Leftward rotate
		Node *l = cur->lc;
		cur->lc = cur->rc, cur->rc = cur->lc->rc;
		cur->lc->rc = cur->lc->lc, cur->lc->lc = l;
		cur->lc->update();
	}
}

inline void maintain(Node *cur){
	if(cur->isleaf()) return;
	if(cur->lc->size > cur->rc->size * ratio) rotate(cur, 0);
	if(cur->rc->size > cur->lc->size * ratio) rotate(cur, 1);
}

Node *stk[MAXN];
int tops = 0;

inline void insert(Node *&root, int v){
	if(root == NULL) {root = newNode(v, 1, NULL, NULL); return;}
	Node *cur = root;
	while(true){
		stk[++tops] = cur;
		if(cur->isleaf()){
			cur->lc = newNode(min(v, cur->val), 1, NULL, NULL);
			cur->rc = newNode(max(v, cur->val), 1, NULL, NULL);
			break;
		}
		if(v > cur->lc->val) cur = cur->rc;
		else cur = cur->lc;
	}
	while(tops) stk[tops]->update(), maintain(stk[tops--]);
}

inline void erase(Node *&root, int v){
	if(root == NULL) return;
	Node *cur = root, *fa = root;
	while(true){
		if(cur == NULL) return;
		if(cur->isleaf()){
			if(cur->val == v){
				if(cur == root) root = NULL;
				else if(cur == fa->lc) *fa = *fa->rc;
				else *fa = *fa->lc;
				break;
			}
		}
		else{
			stk[++tops] = cur;
			if(v > cur->lc->val) fa = cur, cur = cur->rc;
			else fa = cur, cur = cur->lc;
		}
	}
	while(tops) stk[tops]->update(), maintain(stk[tops--]);
}

inline int rnk(Node *cur, int v){
	int res = 0;
	while(true){
		if(cur->isleaf()){
			if(v > cur->val) return res + 2;
			return res + 1;
		}
		else{
			if(v > cur->lc->val) res += cur->lc->size, cur = cur->rc;
			else cur = cur->lc;
		}
	}
}

inline int kth(Node *cur, int k){
	while(true){
		if(cur->isleaf()) return cur->val;
		else{
			if(k > cur->lc->size) k -= cur->lc->size, cur = cur->rc;
			else cur = cur->lc;
		}
	}
}

int main(){
	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) putint(rnk(root, x)), nextline();
		else if(opt == 4) putint(kth(root, x)), nextline();
		else if(opt == 5) putint(kth(root, rnk(root, x) - 1)), nextline();
		else if(opt == 6) putint(kth(root, rnk(root, x + 1))), nextline();
	}
	return 0;
}

BZOJ,宗法树

ACommeAmuor 2018-02-22 18:04回复
让宗法树（zyf树）火遍全中国！

willem 2018-02-22 21:40回复
宗法革命尚未成功，全谷同志还需努力 !!! 【大雾

p_b_p_b 2018-03-10 20:12回复
让宗法树（zyf树）火遍全中国！
nzhtl1477 2018-08-27 20:35回复
你扯淡吧，为什么时候叫过“宗法树”这种如此难听的名字了。。。别给我扣帽子啊

willem 2018-08-30 15:28回复
嘤嘤嘤，被dalao表死了

Noire02 2019-03-14 16:03回复
所以这种树学名叫什么。。。

willem 2019-07-07 10:49回复
不知道。lxldalao发明的问他

Willem's Blog

宗法树模板

Problem:

Description

Input

Output

Sample Input

Sample Output

HINT

Code: O(nlogn) [7548K, 364MS]

Optimized Code: O(nlogn) [70344K, 200MS]

评论

ACommeAmuor 2018-02-22 18:04回复

willem 2018-02-22 21:40回复

p_b_p_b 2018-03-10 20:12回复

nzhtl1477 2018-08-27 20:35回复

willem 2018-08-30 15:28回复

Noire02 2019-03-14 16:03回复

willem 2019-07-07 10:49回复

发表评论点击这里取消回复。

Willem's Blog

宗法树模板

Problem:

Description

Input

Output

Sample Input

Sample Output

HINT

Code: O(nlogn) [7548K, 364MS]

Optimized Code: O(nlogn) [70344K, 200MS]

评论

ACommeAmuor 2018-02-22 18:04回复

willem 2018-02-22 21:40回复

p_b_p_b 2018-03-10 20:12回复

nzhtl1477 2018-08-27 20:35回复

willem 2018-08-30 15:28回复

Noire02 2019-03-14 16:03回复

willem 2019-07-07 10:49回复

发表评论 点击这里取消回复。

发表评论点击这里取消回复。