# 宗法树模板

• 2018-02-11
• 0
• 7

## Problem:

Time Limit: 10 Sec  Memory Limit: 128 MB

### Description

1. 插入x数
2. 删除x数(若有多个相同的数，应只删除一个)
3. 查询x数的排名(若有多个相同的数，应输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

```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

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;
}
```

#### 评论

• ###### 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发明的问他

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai