# 替罪羊树模板

• 2018-04-09
• 0

• 当左子树（或右子树）的总节点数大于整棵树总节点数的 α 倍时，认定当前树不平衡，需要重构。其中 α 通常选取 [0.6, 0.8] 区间上的数。
• max(cov[lc[u]], cov[rc[u]]) > cov[u] * α
• 当整棵树中被删除的节点数大于总节点数的一半时，认定当前树冗余信息过多，需要重构。
• sz[u] * 2 < cov[u]

## Code: O(nlogn) [6964K, 324MS]

```// 替罪羊树 (2018.3.5)
// BZOJ 3224 普通平衡树
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<algorithm>
#define MAXN 100005
using namespace std;

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;
int root, val[MAXN << 1], sz[MAXN << 1], cov[MAXN << 1], lc[MAXN << 1], rc[MAXN << 1];
bool exi[MAXN << 1];
int fl[MAXN << 1], topfl;
int bin[MAXN << 1], topbin = 0;

inline int newNode(int v, int s, int c, int l, int r){
static int topp = 0;
int u = topbin ? bin[topbin--] : ++topp;
val[u] = v, sz[u] = s, cov[u] = c, lc[u] = l, rc[u] = r, exi[u] = 1;
return u;
}

inline void delNode(int u) {bin[++topbin] = u;}

inline bool balanced(int u) {return max(cov[lc[u]], cov[rc[u]]) <= cov[u] * 0.75 + 5;}  // 平衡因子取 0.75

inline void update(int u) {sz[u] = sz[lc[u]] + sz[rc[u]] + exi[u], cov[u] = cov[lc[u]] + cov[rc[u]] + 1;}

inline void flatten(int u){
if(lc[u]) flatten(lc[u]);
if(exi[u]) fl[++topfl] = u; else delNode(u);
if(rc[u]) flatten(rc[u]);
}

inline int pullup(int l, int r){
if(l > r) return 0;
int mid = l + r >> 1, u = fl[mid];
lc[u] = pullup(l, mid - 1), rc[u] = pullup(mid + 1, r);
return update(u), u;
}

inline void rebuild(int &u) {topfl = 0, flatten(u), u = pullup(1, topfl);}

inline int* insert(int &u, int v){
if(!u) return u = newNode(v, 1, 1, 0, 0), (int*)NULL;
else{
sz[u]++, cov[u]++; int *sub;
if(v < val[u]) sub = insert(lc[u], v);
else sub = insert(rc[u], v);
return balanced(u) ? sub : &u;
}
}

//inline void erase(int u, int v){  // Erase with value
//	if(!u) return;
//	sz[u]--;
//	if(exi[u] && v == val[u]) {exi[u] = 0; return;}
//	else{
//		if(v < val[u]) erase(lc[u], v);
//		else erase(rc[u], v);
//	}
//}
/* Wrong Answer - Cannot assert whether v is in the left or right subtree when (exi[u] == false && v == val[u]). */

inline void erase(int u, int k){  // Erase with rank
sz[u]--;
if(exi[u] && k == sz[lc[u]] + 1) {exi[u] = 0; return;}
else{
if(k <= sz[lc[u]] + exi[u]) erase(lc[u], k);
else erase(rc[u], k - sz[lc[u]] - exi[u]);
}
}

inline int rnk(int u, int v){
int res = 1;
while(u){
if(v <= val[u]) u = lc[u];
else res += sz[lc[u]] + exi[u], u = rc[u];
}
return res;
}

inline int kth(int u, int k){
while(u){
if(exi[u] && k == sz[lc[u]] + 1) return val[u];
if(k <= sz[lc[u]]) u = lc[u];
else k -= sz[lc[u]] + exi[u], u = rc[u];
}
}

int main(){
getint(n);
for(register int i = 1; i <= n; i++){
getint(opt), getint(x);
if(opt == 1){
int *p = insert(root, x);
if(p) rebuild(*p);
}
else if(opt == 2){
erase(root, rnk(root, x));
if(sz[root] * 2 < cov[root]) rebuild(root);
}
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;
}
```

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