完蛋啦 WBLT 被卡常啦 /ll /ll

· · 算法·理论

编的神秘小故事：

比赛最后想出神秘平衡树做法，写了一发 WBLT 通过样例，但交上去和 O(n^2) 一个分，而且时间来不及啦 /ll /ll

这时候我们就需要~通过一些乱搞~给 ~WBLT~ Leafy Tree 加速了！1111

一、连续内存访问

如果是写了一堆数组，改成结构体以加速内存访问 111

int ls[M], rs[M], sz[M], rev[M];

变成：

struct WBLT {
    int ls, rs, sz, rev;
} t[M];

并且有些时候节点太多也会导致内存访问变慢，可以考虑垃圾回收使得节点数变少或维持在 2n。

课后作业（迫真）试试看：

不使用底层分块线段树，使用 WBLT 冲过 P7447 [Ynoi2007] rgxsxrs

二、维护平衡需要代价

维护平衡是需要代价的，这就导致了 WBLT 某些时候会比非重量平衡的平衡树更慢。

那考虑不在维护平衡树上花费太多的代价呢？

将 \alpha 调小或者直接不维护平衡？

两者虽然复杂度都不对，但是经过测试，前者会使 WBLT 速度更快，而后者在随机数据下会表现得比前者还要快！

int merge(int u, int v) {
    if(! u || ! v) return u | v;
    if(t[u].sz <= t[v].sz * 4 && t[v].sz <= t[u].sz * 4) {
        return up(u, v);
    }
    if(t[u].sz >= t[v].sz) {
        down(u);
        int l = t[u].ls, r = t[u].rs;
        if(t[l].sz * 5 >= (t[u].sz + t[v].sz)) return merge(l, merge(r, v));
        down(r);
        return merge(merge(l, t[r].ls), merge(t[r].rs, v));
    }
    else {
        down(v);
        int l = t[v].ls, r = t[v].rs;
        if(t[r].sz * 5 >= (t[u].sz + t[v].sz)) return merge(merge(u, l), r);
        down(l);
        return merge(merge(u, t[l].ls), merge(t[l].rs, r));
    }
}
int merge(int u, int v) {
    if(! u || ! v) return u | v;
    return up(u, v);
}

下面是一些我的实现，以一个二元组表示测试点的最大值和总和：

在 P3391 【模板】文艺平衡树 (n=10^5) 中，不维护平衡的 Leafy Tree 情况是 (96\mathrm{ms},252\mathrm{ms})，可以和顶尖实现的 splay 比肩了。

在 P5055 【模板】可持久化文艺平衡树 (n=2\times 10^5) 中，维护弱平衡的 Leafy Tree 的情况是 (272\mathrm{ms},3.45\mathrm{s})。

在 P5586 [P5350] 序列 (加强版) (n=3\times 10^5) 中，不维护平衡的 Leafy Tree 情况是 (766\mathrm{ms},3.51\mathrm{s})。

三、线段树也是 Leafy Tree

所以 Leafy Tree 的很多操作可以像线段树一样做，比如求区间和并不需要分裂，直接像线段树一样做就行了。

int query(int u, int l, int r) {
    if(! u) return 0;
    chmax(l, 1); chmin(r, t[u].sz);
    if(r - l + 1 == t[u].sz) return t[u].F;
    int res = 0;
    down(u);
    int mid = t[t[u].ls].sz;
    if(l <= mid) Add(res, query(t[u].ls, l, r));
    if(mid < r) Add(res, query(t[u].rs, l - mid, r - mid));
    return res; 
}

总结

警惕：除了结构体，其他的都是乱搞

但是 OI 现在也需要乱搞（迫真

还有一点就是当 pushup 常数很大的时候，WBLT 貌似会变很慢？（未知

以上就是我最常用的乱搞了，欢迎挑战我搞的几个最优解（喜