解决 Dynamic Rankings，但是用在线 polylog 算法做到 O(n) 空间

__staring__ · 2025-07-01 15:50:24 · 算法·理论

前言

知周所众，Dynamic Rankings 的一些常见 polylog 做法是（这里认为 n,q 同阶，\log{V},\log{n} 同阶）：

树状数组套值域线段树，在线，时间 O(n\log^2{n})，空间 O(n\log^2{n})。
整体二分套树状数组，离线，时间 O(n\log^2{n})，空间 O(n)。
值域线段树套平衡树，在线，时间 O(n\log^2{n})，空间 O(n\log{n})。

看来时间上不太好优化了，但是空间上，线性的不能在线，在线的不能线性，这看上去就比时间好优化！

那么我们该选择哪个算法优化呢？欸，我们都不用👆🤓。

众所不一定周知，静态区间排名除了使用主席树和整体二分，还可以使用小波矩阵 (Wavelet Matrix)，如果你不了解小波矩阵是什么，这里自荐我的小波矩阵专栏。

小波矩阵该如何实现单点修改？只需把内层的 bitset 替换为平衡树，即可做到在线时间 O(n\log^2{n}) 空间 O(n\log{n})（你也可以认为这是小波矩阵套平衡树）。

为什么选择小波矩阵？因为内层的数据结构维护的信息只有 0/1！如果内层的数据结构可以做到 O(\frac{n}{\omega}) 之类的空间，我们的总空间就是线性的！

问题

因此我们现在需要解决的问题是：

维护可变长 01 序列 a_i，记序列长度为 n，要求低于 O(n) 空间，单次 O(\log{n}) 时间维护 q 次操作：

由于有插入删除，使用平衡树维护序列，方便起见，我们使用替罪羊树，记平衡因子为 \alpha。

不妨还是考虑 bitset 的压位存储（记字长 \omega=32），但是若每个块固定对应了一段原序列，插入删除时需要对 O(\frac{n}{\omega}) 个块进行左右移。

因此我们考虑动态底层分块，令每个块维护 [1,64] 个 bit，并保证块的中序遍历等价于原序列。

记 n 为序列长度（总 bit 数），m 为总节点数。

struct NODE
{
    short lc, rc; // 左右子节点
    ULL val; int bit; // 块内维护的 bit 和个数（0-index）
    int subn, subb, subs; // 子树内的节点数、bit 数、bit 和
};

short tot, top, rt;
vector <NODE> tr;
vector <short> stk;
static vector <ULL> val; // 辅助空间
static mt19937 rnd;
static ULL bin[65]; // bin[i]=2^i-1，即只有 [0,i) 位为 1 的二进制数
int p1, p2; // 辅助变量

#define ppcll __builtin_popcountll

scapegoatTree(int n)
{
    // 由于只需要 O(n/w) 的空间，因此可以使用 short 存储节点编号
    // 同时为了保证空间为 O(n/w)，需要进行垃圾回收
    tot = top = rt = 0;
    n = n + 64 >> 5;
    tr.resize(n);
    stk.resize(n);
}

int create(ULL v, int c)
{
    int x = top ? stk[top --] : ++tot;
    return tr[x] = {0, 0, v, c, 0, 0, 0}, x;
}

void pushup(int x)
{
    tr[x].subn = 1 + tr[tr[x].lc].subn + tr[tr[x].rc].subn;
    tr[x].subb = tr[x].bit + tr[tr[x].lc].subb + tr[tr[x].rc].subb;
    tr[x].subs = ppcll(tr[x].val) + tr[tr[x].lc].subs + tr[tr[x].rc].subs;
}

重构

令重构后每个节点维护 64bit，这可以使用一点位运算简单做到 O(\text{subn}_x+\frac{\text{subb}_x}{\omega})=O(\text{subn}_x)。

// val p1 p2 表示目前 val[p1] 的第 p2 位还没有存储 bit
void flatten(int x)
{
    if(!x) return;
    flatten(tr[x].lc);
    if(tr[x].bit)
    {
        stk[++top] = x;
        val[p1] |= tr[x].val << p2;
        if(p2 + tr[x].bit >= 64)
        {
            val[++p1] = p2 ? tr[x].val >> 64 - p2 : 0;
            p2 -= 64;
        }
        p2 += tr[x].bit;
    }
    flatten(tr[x].rc);
}

int build(int l, int r)
{
    if(l > r) return 0;
    int m = (l + r) >> 1;
    int x = create(val[m], m < p1 ? 64 : p2);
    tr[x].lc = build(l, m - 1);
    tr[x].rc = build(m + 1, r);
    return pushup(x), x;
}

void rebuild(short &x)
{
    p1 = 1, val[1] = p2 = 0;
    flatten(x);
    x = build(1, p1 - !p2);
}

查询

从根节点开始二分，终节点处使用 __builtin_popcountll 即可。

int rankin(int k)
{
    int x = rt, res = 0;
    while(x)
        if(k < tr[tr[x].lc].subb)
            x = tr[x].lc;
        else if(res += tr[tr[x].lc].subs, k -= tr[tr[x].lc].subb; k >= tr[x].bit)
            res += ppcll(tr[x].val), k -= tr[x].bit, x = tr[x].rc;
        else break;
    return res + ppcll(tr[x].val << (63 - k));
}

插入

找到对应插入的节点，若 <64bit 就直接插入，否则考虑将首 bit 移动到左子树的最右节点插入，或将尾 bit 移动到右子树的最左节点插入，两者随机选择，若为空节点则新建。

注意上述流程可能进行不止一遍。

由于这是替罪羊树，当新节点深度超过 \log_{1/\alpha}{m}（m 为插入后的节点数）时，则在回溯时找到第一个失衡的节点重构子树，节点 x 失衡当且仅当（与常规定义相同）：

\max\{\text{nod}_{\text{left}(x)},\text{nod}_{\text{right}(x)}\}>\alpha\cdot\text{nod}_x

由于只稍微修改了替罪羊树的插入，因此插入部分仍可认为复杂度与替罪羊树相同，即均摊 O(\log{n})。

实测得到，当 \alpha=0.5 时运行速度最快，因此下面的代码进行了一定程度的简化。

void putin(ULL &val, int k, ULL v) // 在 val 的第 k 位前插入 v
{
    val = (val & bin[k]) | (v << k) | ((val & ~bin[k]) << 1);
}

int insert(short &x, int k, ULL v, int d)
{
    static ULL tmp, l, r;
    int check = 0, down = 0;
    if(!x)
    {
        x = create(v, 1);
        check = 1ull << d > tr[rt].subn + 1;
    }
    else if(k < tr[tr[x].lc].subb)
        down = -1;
    else if(k -= tr[tr[x].lc].subb; k > tr[x].bit)
        k -= tr[x].bit, down = 1;
    else if(tr[x].bit < 64)
        putin(tr[x].val, k, v), ++tr[x].bit;
    else
    {
        tmp = (tr[x].val & bin[63]) >> 1;
        l = tr[x].val & 1, r = tr[x].val >> 63 & 1;
        if(k == 0) tmp = tmp << 1 | l, l = v;
        else if(k == 64) tmp |= r << 62, r = v;
        else --k, putin(tmp, k, v);

        if(rand() & 1)
            tr[x].val = tmp << 1 | l, k = 0, v = r, down = 1;
        else tr[x].val = tmp | r << 63, k = tr[tr[x].lc].subb, v = l, down = -1;
    }
    if(down) check = insert(down < 0 ? tr[x].lc : tr[x].rc, k, v, d + 1);
    pushup(x);

    if(check && (
        tr[tr[x].lc].subn << 1 > tr[x].subn ||
        tr[tr[x].rc].subn << 1 > tr[x].subn))
        return rebuild(x), 0;
    return check;
}

void insert(int k, int v)
{
    insert(rt, k, v, 0);
}

删除

删除时，找到对应删除的节点直接删除此 bit，同样地，节点为空时不删除节点，等待后续插入或是重构。

由于空节点过多对时间复杂度影响不大（从 O(\log{m}) 上升到 O(\log{q})），因此删除操作的整体重构主要是为了保证空间复杂度。

具体的，我们希望总是保证 m \le \frac{n}{\omega}，因此若某次操作后 m\cdot\omega > n，则对整棵树进行重构，接下来对于整体重构的复杂度，我们做并不严谨的简要说明。

考虑上次重构至当前重构期间，假设没有插入操作，那么至少删除了一半的 bit，即 O(n) 次操作，而当插入操作新建节点时，仍可以分析得到进行 O(n) 次操作才会触发重构，而一次重构可以做到 O(m+\frac{n}{\omega})=O(m)，因此删除操作的均摊复杂度也是 O(\log{n})。

void remove(int x, int k)
{
    if(k < tr[tr[x].lc].subb)
        remove(tr[x].lc, k);
    else if(k -= tr[tr[x].lc].subb; k >= tr[x].bit)
        remove(tr[x].rc, k - tr[x].bit);
    else
    {
        tr[x].val = (tr[x].val & bin[k]) | (tr[x].val >> 1 & ~bin[k]);
        --tr[x].bit;
    }
    pushup(x);
}

void remove(int k)
{
    remove(rt, k);
    if(tr[rt].subn << 5 > tr[rt].subb)
        rebuild(rt);
}

应用

把这个平衡树应用到小波矩阵上，我们就获得了在线时间 O(n\log^2{n}) 空间 O(\frac{n\log{n}}{\omega})=O(n) 的动态排名做法！完整代码与提交记录。

既然动态区间 k 小可以做，那么稍微改改就能做树套树模板题了。

可以发现这个做法天生支持插入，于是额外用 fhq treap 维护原序列，再改改就能做带插入区间 k 小。

真是可喜可贺，可喜可贺……吗？

可以发现，虽然我们确实做到了上述复杂度，~~但是大概由于笔者的代码太抽象~~，其巨大常数和巨大码长在常态下难以接受（拜托我一年前的树套树都能暴打这个做法），因此这个做法更多的是提供一种理论用途。

当然，希望各位读者可以提出常数更小码长更短的算法，这篇文章只是展示了拓展小波矩阵的一种可能性。

扩展

咕咕咕……