WBLT 入门

· · 个人记录

同步一下之前发在 OI wiki 上的版本。

前言

Weight Balanced Leafy Tree，下称 WBLT，是一种平衡树，比起其它平衡树主要有实现简单、常数小的优点。

Weight Balanced Leafy Tree 顾名思义是 Weight Balanced Tree 和 Leafy Tree 的结合。

Weight Balanced Tree 的每个结点储存这个结点下子树的大小，并且通过保持左右子树的大小关系在一定范围来保证树高。

Leafy Tree 维护的原始信息仅存储在树的 叶子节点 上，而非叶子节点仅用于维护子节点信息和维持数据结构的形态。我们熟知的线段树就是一种 Leafy Tree。

平衡树基础操作

代码约定

下文中，我们用 ls[x] 表示节点 x 的左儿子，rs[x] 表示节点 x 的右儿子，vl[x] 表示节点 x 的权值，sz[x] 表示节点 x 及其子树中叶子节点的个数。

建树

正如前言中所说的，WBLT 的原始信息仅存储在叶子节点上。而我们规定每个非叶子节点一定有两个子节点，这个节点要维护其子节点信息的合并。同时，每个节点还要维护自身及其子树中叶子节点的数量，用于实现维护平衡。

和大多数的平衡树一样，每个非叶子节点的右儿子的权值大于等于左儿子的权值，且在 WBLT 中非叶子节点节点的权值等于右儿子的权值。不难看出每个节点的权值就是其子树中的最大权值。

这样听起来就很像一棵维护区间最大值的动态开点线段树了，且所有叶子从左到右是递增的。事实上的建树操作也与线段树十分相似，只需要向下递归，直至区间长度为 1 时把要维护的信息放叶子节点上，回溯的时候合并区间信息即可。

代码实现如下：

/* 添加一个权值为 v 的节点，返回这个节点的编号 */
int add(int v) {
  ++cnt;
  ls[cnt] = rs[cnt] = 0;
  sz[cnt] = 1;
  vl[cnt] = v;
  return cnt;
}

/* 更新节点编号为 x 的节点的信息 */
void pushup(int x) {
  vl[x] = vl[rs[x]];
  sz[x] = sz[ls[x]] + sz[rs[x]];
}

/* 递归建树 */
int build(int l, int r) {
  if (l == r) {
    return add(a[l]);
  }
  int x = add(0);
  int k = l + ((r - l) >> 1);
  ls[x] = build(l, k);
  rs[x] = build(k + 1, r);
  pushup(x);
}

插入和删除

由于 WBLT 的信息都存储在叶子节点上，插入和删除一个元素其实就是增加或减少了一个叶子节点。

对于插入操作，我们类似从根节点开始向下递归，直到找到权值大于等于插入元素的权值最小的叶子节点，再新建两个节点，其中一个用来存储新插入的值，另一个作为两个叶子的新父亲替代这个最小叶子节点的位置，再将这两个叶子连接到这个父亲上。

例如我们向以下树中加入一个值为 4 的元素。

我们首先找到了叶子节点 5，随后新建了一个非叶子节点 D，并将 4 和 5 连接到了 D 上。

对于删除，我们考虑上面过程的逆过程。即找到与要删除的值权值相等的一个叶子节点，将它和它的父亲节点删除，并用其父亲的另一个儿子代替父亲的位置。

上面提到的建树也可以通过不断往树里插入节点实现，不过如果这样做必须要加入一个权值为 \infty⁡ 的节点作为根，否则会导致插入第一个元素的时候找不到大于自己的叶子节点。

代码实现：

/* 将某一节点的全部信息复制到另一节点上 */
void copynode(int x, int y) {
  ls[x] = ls[y];
  rs[x] = rs[y];
  sz[x] = sz[y];
  vl[x] = vl[y];
}

/* 判断某一节点是否为叶子节点 */
bool leaf(int x) { return !ls[x] || !rs[x]; }

void insert(int v) {
  if (leaf(x)) {
    ls[x] = add(std::min(v, vl[x]));
    rs[x] = add(std::max(v, vl[x]));
    pushup(x);
    maintain(x);
    return;
  }
  if (vl[ls[x]] >= v) {
    insert(ls[x], v);
  } else {
    insert(rs[x], v);
  }
  pushup(x);
  maintain(x);
}

void delete(int x, int v, int fa) {
  if (leaf(x)) {
    if (ls[fa] == x) {
      copynode(fa, rs[fa]);
    } else {
      copynode(fa, ls[fa]);
    }
    pushup(fa);
    return;
  }
  if (vl[ls[x]] >= v) {
    delete (ls[x], v, x);
  } else {
    delete (rs[x], v, x);
  }
  pushup(x);
  maintain(x);
}

维护平衡

类似替罪羊树地，我们引入重构参数 \alpha \in (0, \dfrac{1}{2}]，我们设一个节点的平衡度 \rho 为当前节点左子树大小和节点大小的比值。当一个节点满足 \rho \in[\alpha, 1-\alpha] 时，我们称其为 \alpha- 平衡的。如果一棵 WBLT 的每一个节点都是 \alpha- 平衡的，那么这棵树的树高一定能保证是 O(\log n) 量级的。证明是显然的，我们从一个叶子节点往父亲方向走，每次走到的节点维护的范围至少扩大到原来的 \dfrac{1}{1 - \alpha} 倍，那么树高就是 O(\log_{\frac{1}{1-\alpha}}n) = O(\log n) 量级的。

当某个节点不满足 \alpha- 平衡时，说明这个节点是失衡的，我们需要重新维护平衡。但是和替罪羊树不同的是，WBLT 使用旋转操作维护平衡。旋转的大致过程为：将过重的儿子的两个儿子拆下来，一个和过轻的儿子合并，另一个成为一个新的儿子。

我们来举个例子：

这是一棵十分不平衡的 WBLT，节点 A 的右儿子显著地重于左儿子。我们先把右儿子及其两个儿子和左儿子都拆下来：

然后，我们将 1 和 2 两个节点合并作为 A 节点的左儿子，将 C 作为 A 的右儿子。由于 B 节点原本并不是叶子节点，因此其并不存储原始信息，直接删除就好。

旋转之后我们的树就变得十分平衡了。

但是上面的例子中，假设 A 节点的左子树过于大，我们把它合并到 A 的左子树上之后 A 的左子树又会很大，这时 A 依然可能不平衡。

不失一般性，我们接下来仅讨论一个方向上的旋转，另一方向的旋转是对称的。我们不妨设 A 的平衡度为 \rho_1，B 的平衡度为 \rho_2。那么我们可以得到旋转后 A 的平衡度 \gamma_1= \rho_1+(1 - \rho_1)\rho_2，B 的平衡度 \gamma_2 =\dfrac{\rho_1}{\rho_1 + (1 - \rho_1)\rho_2}，推导过程直接将各节点大小用 siz_A 表示后代入定义式化简即可，这里略去。

不难发现仅当 \rho_2 \le \dfrac{1 - 2\alpha}{1 - \alpha} 时 \gamma_1, \gamma_2 \in [\alpha, 1 - \alpha]。

为了旋转后仍不平衡的情况出现，我们引入双旋操作。具体地，我们在较大子树上做一次相反方向的旋转操作，然后再维护当前节点的平衡。

类似地定义 \rho_3,\gamma_3，则有 \gamma_1=\rho_1+\rho_2\rho_3(1-\rho_3), \gamma_2=\dfrac{\rho_1}{\rho1+(1 - \rho_1)\rho2\rho3}, \gamma_3 = \dfrac{\rho_2(1-\rho_3)}{1-\rho_2\rho_3}。可以证明当 \alpha < 1- \dfrac{\sqrt2}{2} \approx 0.292 时一定有 \gamma_1, \gamma_2, \gamma_3 \in [\alpha, 1 - \alpha]。

实现上，我们在 \rho_2 \le \dfrac{1 - 2\alpha}{1 - \alpha} 时进行单旋，否则进行双旋。

代码实现，这里取 \alpha = 0.25：

const double alpha = 0.25;

void rotate(int x, int flag) {
  if (!flag) {
    rs[x] = merge(rs[ls[x]], rs[x]);
    ls[x] = ls[ls[x]];
  } else {
    ls[x] = merge(ls[x], ls[rs[x]]);
    rs[x] = rs[rs[x]];
  }
}

void maintain(int x) {
  if (sz[ls[x]] > sz[rs[x]] * 3) {
    if (sz[rs[ls[x]]] > sz[ls[ls[x]]] * 2) {
      rotate(ls[x], 1);
    }
    rotate(x, 0);
  } else if (sz[rs[x]] > sz[ls[x]] * 3) {
    if (sz[ls[rs[x]]] > sz[rs[rs[x]]] * 2) {
      rotate(rs[x], 0);
    }
    rotate(x, 1);
  }
}

查询排名

我们发现 WBLT 的形态和线段树十分相似，因此查询排名可以使用类似线段树上二分的方式：如果左子树的最大值比大于等于待查值就往左儿子跳，否则就向右跳，同时答案加上左子树的 size。

int rank(int x, int v) {
  if (leaf(x)) {
    return 1;
  }
  if (vl[ls[x]] >= v) {
    return rank(ls[x], v);
  } else {
    return rank(rs[x], v) + sz[ls[x]];
  }
}

查询第 k 大的数

依然是利用线段树上二分的思想，只不过这里比较的是节点的大小。

int kth(int x, int v) {
  if (sz[x] == v) {
    return vl[x];
  }
  if (sz[ls[x]] >= v) {
    return kth(ls[x], v);
  } else {
    return kth(rs[x], v - sz[ls[x]]);
  }
}

总结

以上，我们利用 WBLT 完成了平衡树基本的几大操作。下面是用 WBLT 实现的 普通平衡树模板。

#include <bits/stdc++.h>

typedef long long ll;

const ll MAX = 2e6 + 5;
const ll INF = 0x7fffffff;

ll ans, lst, n, m, t, op, rt, cnt;
ll ls[MAX], rs[MAX], vl[MAX], sz[MAX];

void cp(ll x, ll y) {
  ls[x] = ls[y];
  rs[x] = rs[y];
  sz[x] = sz[y];
  vl[x] = vl[y];
}

ll add(ll v, ll s, ll l, ll r) {
  ++cnt;
  ls[cnt] = l;
  rs[cnt] = r;
  sz[cnt] = s;
  vl[cnt] = v;
  return cnt;
}

ll merge(ll x, ll y) { return add(vl[y], sz[x] + sz[y], x, y); }

void upd(ll x) {
  if (!ls[x]) {
    sz[x] = 1;
    return;
  }
  sz[x] = sz[ls[x]] + sz[rs[x]];
  vl[x] = vl[rs[x]];
}

void rot(int x, int flag) {
  if (!flag) {
    rs[x] = merge(rs[ls[x]], rs[x]);
    ls[x] = ls[ls[x]];
  } else {
    ls[x] = merge(ls[x], ls[rs[x]]);
    rs[x] = rs[rs[x]];
  }
}

void mat(int x) {
  if (sz[ls[x]] > sz[rs[x]] * 3) {
    if (sz[rs[ls[x]]] > sz[ls[ls[x]]] * 2) {
      rot(ls[x], 1);
    }
    rot(x, 0);
  } else if (sz[rs[x]] > sz[ls[x]] * 3) {
    if (sz[ls[rs[x]]] > sz[rs[rs[x]]] * 2) {
      rot(rs[x], 0);
    }
    rot(x, 1);
  }
}

void ins(ll x, ll v) {
  if (!ls[x]) {
    ls[x] = add(std::min(v, vl[x]), 1, 0, 0);
    rs[x] = add(std::max(v, vl[x]), 1, 0, 0);
    upd(x);
    mat(x);
    return;
  }
  if (vl[ls[x]] >= v) {
    ins(ls[x], v);
  } else {
    ins(rs[x], v);
  }
  upd(x);
  mat(x);
  return;
}

void del(ll x, ll v, ll fa) {
  if (!ls[x]) {
    if (vl[ls[fa]] == v) {
      cp(fa, rs[fa]);
    } else if (vl[rs[fa]] == v) {
      cp(fa, ls[fa]);
    }
    return;
  }
  if (vl[ls[x]] >= v) {
    del(ls[x], v, x);
  } else {
    del(rs[x], v, x);
  }
  upd(x);
  mat(x);
  return;
}

ll rnk(ll x, ll v) {
  if (sz[x] == 1) {
    return 1;
  }
  if (vl[ls[x]] >= v) {
    return rnk(ls[x], v);
  } else {
    return rnk(rs[x], v) + sz[ls[x]];
  }
}

ll kth(ll x, ll v) {
  if (sz[x] == v) {
    return vl[x];
  }
  if (sz[ls[x]] >= v) {
    return kth(ls[x], v);
  } else {
    return kth(rs[x], v - sz[ls[x]]);
  }
}

ll pre(ll x) { return kth(rt, rnk(rt, x) - 1); }

ll nxt(ll x) { return kth(rt, rnk(rt, x + 1)); }

int main() {
  scanf("%lld", &m);
  rt = add(INF, 1, 0, 0);
  while (m--) {
    scanf("%lld%lld", &op, &t);
    if (op == 1) {
      ins(rt, t);
    } else if (op == 2) {
      del(rt, t, -1);
    } else if (op == 3) {
      printf("%lld\n", rnk(rt, t));
    } else if (op == 4) {
      printf("%lld\n", kth(rt, t));
    } else if (op == 5) {
      printf("%lld\n", pre(t));
    } else {
      printf("%lld\n", nxt(t));
    }
  }
  return 0;
}