重量平衡树

维护一个序列，支持 \(O(\log n)\) 插入删除，\(O(1)\) 比较两个数的前后位置，我们可以为每个节点维护一个权值 \(val[x]\)，两个子节点的权值分别是 \(val[x]-\frac{1}{2}\operatorname{lowbit}(val[x])\) 和 \(val[x]+\frac{1}{2}\operatorname{lowbit}(val[x])\)，只要树高不太高，权值就可以在 unsigned long long 范围内存下。

问题是 fhq 的分裂合并还是 treap 和 splay 的 rotate，都不能很好的维护上面的信息。考虑一种新的平衡树，插入时直接向下找到插入位置，然后找到受影响的根链上第一个满足 \(\max(sz[lc],sz[rc])>\alpha\times sz[u]\) 的节点 \(u\)，直接把 \(u\) 子树拍平重构。\(\alpha\) 一般取 \([0.7,0.8]\)。

可以证明，这样的平衡树单次操作也是 \(O(\log n)\) 的，并且实现较为简单。

代码

const double alpha = 0.75;
const ull VAL_RT = 1ull << 63;
namespace wbt {
    struct Node {
        ull val; int lc, rc, sz;
    } tr[N]; int nn, rt, buf[N], top;
    inline ull f(ull val) { return (val & -val) >> 1; }
    inline Node &lc(int p) { return tr[tr[p].lc]; }
    inline Node &rc(int p) { return tr[tr[p].rc]; }
    inline int addNode() { tr[++nn] = {0, 0, 0, 1}; return nn; }
    void pa(int p) { if(!p) return; pa(tr[p].lc); buf[++top] = p; pa(tr[p].rc); }
    int build(ull val, int l, int r) {
        if(l > r) return 0;
        if(l == r) return tr[buf[l]] = {val, 0, 0, 1}, buf[l];
        int mid = (l + r) >> 1, cur = buf[mid];
        tr[cur] = {val, build(val - f(val), l, mid - 1), build(val + f(val), mid + 1, r), 0};
        tr[cur].sz = lc(cur).sz + rc(cur).sz + 1;
        return cur;
    }
    void insert(int &p, int k, ull val = VAL_RT, bool flag = false) {
        if(!p) return assert(k == 1), tr[p = addNode()].val = val, void();
        ++tr[p].sz;
        if(k <= lc(p).sz + 1) {
            bool tag = !flag && max(lc(p).sz + 1, rc(p).sz) >= alpha * tr[p].sz;
            insert(tr[p].lc, k, val - f(val), flag | tag);
            if(tag) pa(p), p = build(val, 1, top), top = 0;
        } else {
            bool tag = !flag && max(lc(p).sz, rc(p).sz + 1) >= alpha * tr[p].sz;
            insert(tr[p].rc, k - lc(p).sz - 1, val + f(val), flag | tag);
            if(tag) pa(p), p = build(val, 1, top), top = 0;
        }
    }
}