Weight Balanced Leafy Tree

Leafy Tree ​

Leafy Tree 是一种 仅 将信息储存在叶子的数据结构。线段树是一种常见的 Leafy Tree。

使用 Leafy Tree 的结构，进行加权维护，可以得到一棵平衡二叉搜索树。

WBLT ​

定义 ​

WBLT 定义为一棵 Leafy Tree，即，叶子节点维护序列中的数值，非叶子节点维护其子树内的最大值。每一个节点具有两个或零个儿子。

$sz_x$ 表示以 $x$ 为根的子树的大小，子树大小定义为子树内叶子的个数（此处定义为节点的个数是等价的，因为节点数量等于叶子数量乘二加一）。

$ls_x$ 表示 $x$ 的左子树，$rs_x$ 表示 $x$ 的右子树。

一个点的 $x$ 平衡度定义为 $\frac{\min(sz_{ls_x}, sz_{rs_x})}{sz_x}$，也就是较小的子树占整棵树的比例。

定义重构参数 $\alpha\in (0,\frac{1}{2}]$，当点 $x$ 的平衡度小于 $\alpha$，也就是较小子树过小时，我们认为点 $x$ 的子树失衡，需要进行平衡维护。否则我们认为 $x$ 子树是平衡的。

重构参数 ​

若 $\alpha$ 过大，则平衡维护次数过多；若 $\alpha$ 过小，则树的深度较大。所以 $\alpha$ 一般适中，取 $0.25$ 可以避免浮点数运算，提升效率。

性质 ​

由于 Leafy Tree 只有叶子存储信息，所以需要大约 $n$ 个非叶子节点，总结点数大约是 $2n$ 的。所以这是 WBLT 的一个缺点，它需要两倍的空间。

根据平衡度与重构参数的定义，当整棵树平衡时，每向父亲走一条边，树的大小至少乘 $\frac{1}{1-\alpha}$，那么总树高是 $O(\log n)$ 的。当 $\alpha=0.25$ 时，这个 $\log$ 大约是以二为底的 $\log$ 的 2 倍。

合并操作 ​

假设合并两棵分别以 $x$ 和 $y$ 为根的 WBLT，需要保证 $x$ 的所有权值不大于 $y$ 的。

不失一般性地，假设 $sz_x\ge sz_y$，另一种情况是对称的。

若 $\frac{sz_y}{sz_x+sz_y}\ge \alpha$，那么此时直接合并即可。

若 $\frac{sz_{ls_x}}{sz_x+sz_y}\ge \alpha$，则递归合并 $x$ 的右儿子和 $y$，再将结果和 $x$ 的左儿子合并即可。

否则，将 $x$ 的左儿子与右儿子的左儿子合并，再将右儿子的右儿子与 $y$ 合并，将这两个结果合并即可。

从上到下分了三种情况，第一种情况是直接满足。当左儿子足够大时，直接将左儿子与剩余部分合并。否则，将左儿子拼上一个右儿子的左儿子，这样就足够大了，再进行合并。

OI-wiki 上说这样合并复杂度是 $O(\log \frac{sz_x}{sz_y})$ 的。

当插入或删除完成之后，可以使用这种操作合并两个子树，来维护平衡。由于树本身是平衡的，插入一个节点之后左右子树大小不会相差太多，所以这样的复杂度应该是常数的。

分裂操作 ​

分裂有按值分裂和按排名分裂两种，但是应该是类似的。

根据子树权值大小决定递归分裂哪一侧。但是为了保证树的平衡，需要使用 merge 函数进行合并。

其它操作 ​

其它操作基于分裂合并，并不是很难做。例如插入操作，可以懒惰地写作，先分裂，插入后，再分裂。

代码实现 ​

节点定义 ​

struct Node {
  int val, sz;
  Node *ls, *rs;
  Node() : val(0), sz(0), ls(nullptr), rs(nullptr) {}
  Node(int v) : val(v), sz(1), ls(nullptr), rs(nullptr) {}
  Node(Node *l, Node *r) : val(0), sz(0), ls(l), rs(r) {
    if (l != nullptr) val = max(val, l->val), sz += l->sz;
    if (r != nullptr) val = max(val, r->val), sz += r->sz;
  }
  bool leaf() {
    return ls == nullptr;
  }
} pool[OP_CNT << 1];
size_t pool_cnt;
Node *new_node(Node v) {
  return &(pool[pool_cnt++] = v);
}

注意在有多个相同的值时，用不同的节点储存相同的值，防止无法平衡。

合并操作 ​

void merge(Node *rt, Node *u, Node *v) {
  if (u == nullptr) return void(*rt = *v);
  if (v == nullptr) return void(*rt = *u);
  int w = u->sz + v->sz;
  if (min(u->sz, v->sz) * 10 >= w * 3) return void(*rt = Node(u, v));
  if (u->sz > v->sz) {
    if (u->ls->sz * 10 >= w * 3) {
      Node *t = u->ls;
      merge(u, u->rs, v);
      return void(*rt = Node(t, u));
    }
    Node *t1 = u->rs, *t2 = u->rs->rs;
    merge(u, u->ls, u->rs->ls);
    merge(t1, t2, v);
    return void(*rt = Node(u, t1));
  }
  if (v->rs->sz * 10 >= w * 3) {
    Node *t = v->rs;
    merge(v, u, v->ls);
    return void(*rt = Node(v, t));
  }
  Node *t1 = v->ls, *t2 = v->ls->ls;
  merge(v, v->ls->rs, v->rs);
  merge(t1, u, t2);
  return void(*rt = Node(t1, v));
}

合并只修改儿子指针指向的值，而不会修改指针本身，防止造成混乱。

合并时将空余节点进行了利用，防止出现过多垃圾节点，导致空间复杂度不是线性的。另一种写法是进行垃圾回收，但其实回收完之后马上就要再利用了，不如直接利用。

其余操作和二叉搜索树是基本一致的，只是插入和删除时需要合并两个子节点进行平衡维护。

持久化 ​

持久化用路径复制实现，具体来说，修改了某一个节点，就将这个节点拷贝一份。具体实现只需要将 merge 函数修改，原本传入 rt 以回收垃圾节点，现在由于进行了修改，所以需要得到新的 rt，将合并的结果作为返回值即可。

Node *merge(Node *x, Node *y) {
  if (x == nullptr) return y;
  if (y == nullptr) return x;
  int w = x->sz + y->sz;
  if (min(x->sz, y->sz) * 10 >= w * 3) return new_node(Node(x, y));
  if (x->sz > y->sz) {
    if (x->ls->sz * 10 >= w * 3) return new_node(Node(x->ls, merge(x->rs, y)));
    return new_node(Node(merge(x->ls, x->rs->ls), merge(x->rs->rs, y)));
  }
  if (y->rs->sz * 10 >= w * 3) return new_node(Node(merge(x, y->ls), y->rs));
  return new_node(Node(merge(x, y->ls->ls), merge(y->ls->rs, y->rs)));
}

比如说插入就这么写，最后将返回的指针记住，这就是这次操作产生版本的根。

Node *ins(Node *cur, int v) {
  if (cur->leaf()) {
    auto t = minmax(cur->val, v);
    return merge(new_node(t.first), new_node(t.second));
  }
  if (v <= cur->ls->val) return merge(ins(cur->ls, v), cur->rs);
  return merge(cur->ls, ins(cur->rs, v));
}

文艺平衡树 ​

相较于普通平衡树，区间操作要求支持分裂。比较容易弄出问题的一点是：假如分裂的最左侧是某一个点的右叶子，那么将这分离开之后，会出现其父亲只有一个儿子的情况，此时如果左叶子或右叶子和父亲的信息是重叠的，有一个节点是多余的，需要将这个节点回收，否则可能会 MLE。

另一个问题是，将根分裂之后，由于回收机制，根会被利用来放其它东西，这时候，如果合并的根选择原来的根，就会出问题。所以需要新建一个跟来作为新的根。

持久化文艺平衡树 ​

也是类似的。写的时候有些地方没下传标记，挂飞了，调了很久。

持久化文艺平衡树需要下传标记，传标记的时候也需要新建节点。