〇、二叉搜索树（BST, Binary Search Tree）
BST 满足以下性质：
对于节点 \(u\)，他最多只有两个儿子，以左儿子为根的子树中的所有元素小于 \(a_u\)，以右儿子为根的子树中的所有元素大于 \(a_u\)。
可以一直向左儿子跳找到最小值，一直向右儿子跳找到最大值。
BST 的操作作为前置知识，不会可以右转去 OI-Wiki：https://oi-wiki.org/ds/bst/
一、替罪羊树
如果 BST 退化成一条链，查找的时间复杂度就从 \(O(\log n)\) 退化成 \(O(n)\)，如果是一道 DS 题就会被卡到 \(O(nm)\)，显然是我们不能接受的。
怎么办？很简单，如果子树的比例过于不均衡（比如子树的大小 \(siz_{ls_u} > \alpha \times siz_u\)）就当成替罪羊重构就行了。（这也是替罪羊树名字的由来）
关于常数 \(\alpha\) 的取值：\(\alpha\) 越大，重构次数越少，单次查询复杂度越高，所以一般取 \(\alpha = 0.7 \sim 0.75\)。
贴一下代码：
const int N = 1e5 + 5;
struct scapegoat_tree {
double alpha = 0.75;
struct node {
int L, R, val, siz, valid;
bool del;
inline void new_node (int u) {
L = R = 0;
val = u;
siz = valid = 1;
del = false;
}
} tr[N << 2];
int tot = 0, root = 0;
inline bool bad (int u) {
double __std = alpha * tr[u].siz;
int ls = tr[u].L;
int rs = tr[u].R;
if ((double) (tr[ls].siz) > __std) return true;
if ((double) (tr[rs].siz) > __std) return true;
return false;
}
inline void update (int u) {
int ls = tr[u].L;
int rs = tr[u].R;
tr[u].siz = tr[ls].siz + tr[rs].siz + !tr[u].del;
tr[u].valid = tr[ls].valid + tr[rs].valid + !tr[u].del;
}
inline void dfs (int u, vector < int > &st) {
if (!u) return ;
dfs (tr[u].L, st);
if (!tr[u].del) st.push_back (u);
dfs (tr[u].R, st);
return ;
}
inline int build (vector < int > &st, int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
int u = st[mid];
tr[u].L = build (st, l, mid);
tr[u].R = build (st, mid + 1, r);
update (u);
return u;
}
inline void rebuild (int &u) {
vector < int > st;
dfs (u, st);
u = build (st, 0, st.size ());
}
inline void insert_element (int val, int &u) {
if (!u) {
u = ++ tot;
tr[u].new_node (val);
return ;
}
tr[u].siz ++;
tr[u].valid ++;
if (val >= tr[u].val) insert_element (val, tr[u].R);
else insert_element (val, tr[u].L);
if (bad (u)) rebuild (u);
}
inline int rank (int u, int x) {
int ans = 1;
while (u) {
if (tr[u].val >= x) u = tr[u].L;
else {
ans += tr[tr[u].L].valid + !tr[u].del;
u = tr[u].R;
}
}
return ans;
}
inline int kth (int rt, int x) {
while (rt) {
if (!tr[rt].del && tr[tr[rt].L].valid + 1 == x) return tr[rt].val;
if (tr[tr[rt].L].valid >= x) rt = tr[rt].L;
else {
x -= tr[tr[rt].L].valid + !tr[rt].del;
rt = tr[rt].R;
}
}
}
inline void del (int u, int rnk) {
if (!tr[u].del && rnk == tr[tr[u].L].valid + 1) {
tr[u].del = 1;
tr[u].valid --;
return ;
}
tr[u].valid --;
if (rnk <= tr[tr[u].L].valid + !tr[u].del) del (tr[u].L, rnk);
else del (tr[u].R, rnk - tr[tr[u].L].valid - !tr[u].del);
}
} sgt;
讲一下常见的六种操作：
- 插入操作
insert_element (x, root);
- 删除操作
del (root, rank (root, x));
- 查询排名
int result = rank (root, x);
- 查询第 k 大
int result = kth (root, k);
- 查询 x 的前驱
int rk = rank (root, x) - 1;
int result = kth (root, rk);
- 查询 x 的后继
int rk = rank (root, x + 1);
int result = kth (root, rk);
二、Treap
\[\texttt{Treap = Tree + Heap}
\]
将树的结构利用随机优先级的方式重新构建即可降低复杂度。
struct treap {
struct node {int ls, rs, val, pri, cnt, siz;} tr[N];
int root, tot;
inline int create (int w) {
tr[++ tot].val = w;
tr[tot].pri = randomly (1, V), tr[tot].cnt = tr[tot].siz = 1;
return tot;
}
inline void update (int u) {tr[u].siz = tr[u].cnt + tr[tr[u].ls].siz + tr[tr[u].rs].siz;}
inline int rank (int u, int w) {
if (!u) return 0;
if (w == tr[u].val) return tr[tr[u].ls].siz + 1;
if (w < tr[u].val) return rank (tr[u].ls, w);
return rank (tr[u].rs, w) + tr[tr[u].ls].siz + tr[u].cnt;
}
inline int kth (int u, int k) {
if (u == 0) return V;
if (tr[tr[u].ls].siz >= k) return kth (tr[u].ls, k);
if (tr[tr[u].ls].siz + tr[u].cnt >= k) return tr[u].val;
return kth (tr[u].rs, k - tr[tr[u].ls].siz - tr[u].cnt);
}
inline void zig (int &u) {
int v = tr[u].ls;
tr[u].ls = tr[v].rs, tr[v].rs = u, u = v;
update (tr[u].rs), update (u);
}
inline void zag (int &u) {
int v = tr[u].rs;
tr[u].rs = tr[v].ls, tr[v].ls = u, u = v;
update (tr[u].ls), update (u);
}
inline void build () {
create (-V), create (V);
root = 1, tr[root].rs = 2;
if (tr[1].pri < tr[2].pri) zag (root);
}
inline void ins (int &u, int w) {
if (u == 0) {u = create (w); return ;}
if (w == tr[u].val) {tr[u].cnt ++, update (u); return ;}
if (w < tr[u].val) {ins (tr[u].ls, w); if (tr[tr[u].ls].pri > tr[u].pri) zig (u);}
if (w > tr[u].val) {ins (tr[u].rs, w); if (tr[tr[u].rs].pri > tr[u].pri) zag (u);}
update (u);
}
inline int pre (int u, int w) {
if (!u) return -V;
if (w <= tr[u].val) return pre (tr[u].ls, w);
int res = pre (tr[u].rs, w);
return res == -V ? tr[u].val : res;
}
inline int nxt (int u, int w) {
if (!u) return V;
if (w >= tr[u].val) return nxt (tr[u].rs, w);
int res = nxt (tr[u].ls, w);
return res == V ? tr[u].val : res;
}
inline void del (int &u, int v) {
if (!u) {return ;}
if (v == tr[u].val) {
if (tr[u].cnt > 1) {tr[u].cnt --, update (u); return ;}
if (tr[u].ls || tr[u].rs) {
if (tr[u].rs == 0 || tr[tr[u].ls].pri > tr[tr[u].rs].pri) {zig (u), del (tr[u].rs, v);}
else {zag (u), del (tr[u].ls, v);}
update (u);
}
else u = 0; return ;
}
if (v < tr[u].val) {del (tr[u].ls, v);} else {del (tr[u].rs, v);}
update (u);
}
} tre;