宗法树模板
今天种了一棵平衡树,名字已不可考,有可能类似于 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:
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
10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598
Sample Output
106465 84185 492737
HINT
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; }
ACommeAmuor
让宗法树(zyf树)火遍全中国!
willem
宗法革命尚未成功,全谷同志还需努力 !!! 【大雾
p_b_p_b
让宗法树(zyf树)火遍全中国!
nzhtl1477
你扯淡吧,为什么时候叫过“宗法树”这种如此难听的名字了。。。别给我扣帽子啊
willem
嘤嘤嘤,被dalao表死了
Noire02
所以这种树学名叫什么。。。
willem
不知道。lxldalao发明的问他