前序遍历平衡树（？）| 已部分hack，评论中有补充

Gary0 · 2026-10-04 07:27:53 · 算法·理论

以下内容假设最大节点数量 n 与总操作次数 q 同阶。
节点的左子节点的子树简称为左子树，右子节点的子树简称为右子树。

本文将介绍一种常数小，且较难卡到最劣复杂度的数据结构，可以支持大部分一般平衡树支持的操作。

首先，我们注意到已有的几乎所有平衡树都有一个共同的特征——它们的中序遍历序列是单调的。

我们的平衡树一定要废物并且猎奇，怎么能和它们同流合污呢，所以这颗树它的前序遍历序列应该是单调递增的。

于是，我们得到了这棵树的基本性质：每个节点的权值小于其左子节点权值小于其右子节点权值。为了使在这颗树上自根向叶子搜索是可行的，还要要求左儿子子树中的任何节点都小于右儿子。

如此，我们就得到了一颗满足堆性质（虽然没有什么用）的类似二叉搜索树的东西。

那么我们可以写出代码：

:::info[代码（有注释）]

struct tree
{
    int tl, rt;
    struct node { int x, c, sz, l, r; } p[1100006]; // x:节点权值 c:该权值数量 sz:子树大小 l:左子节点 r:右子节点
    inline void pushup(int u) // 更新节点 u 的 sz
    {
        p[u].sz = p[u].c + p[p[u].l].sz + p[p[u].r].sz;
    }
    inline int setnode(int x, int c) // 为 c 个权值 x 创建一个新节点，并返回该节点编号
    {
        int u = ++tl;
        p[u].x = x, p[u].c = p[u].sz = c;
        return u;
    }
    void erasend(int& u) // 删除节点 u，需要使用子节点来补位，可以直接向下递归是因为 erasend 和 eraseat 总共访问的节点数量还是 O(树高) 级别
    {
        if (!p[u].l) { u = p[u].r; return; }
        if (!p[u].r) { u = p[u].l; return; }
        p[u].x = p[p[u].l].x, p[u].c = p[p[u].l].c, erasend(p[u].l);
        pushup(u);
    }
    void insertat(int& u, int x, int c) // 将 c 个权值 x 插入到节点 u 的子树中
    {
        if (!u) { u = setnode(x, c); return; }
        if (x == p[u].x) { p[u].c += c, p[u].sz += c; return; }
        if (x < p[u].x) swap(x, p[u].x), swap(c, p[u].c); // 为方便后续处理，进行下沉操作，即把新节点当做子树根，把原子树根向下沉淀
        if (p[u].r && x >= p[p[u].r].x) insertat(p[u].r, x, c);
        else insertat(p[u].l, x, c);
        pushup(u);
    }
    void eraseat(int& u, int x) // 在节点 u 的子树删除一个权值 x
    {
        if (!u) return;
        if (x == p[u].x && p[u].c > 1) { p[u].c--, p[u].sz--; return; } // 如果权值 x 有好多个就不用动树的结构，直接删掉一个就可以
        if (x == p[u].x) { erasend(u); return; }
        if (p[u].r && x >= p[p[u].r].x) eraseat(p[u].r, x);
        else eraseat(p[u].l, x);
        pushup(u);
    }
    int countlat(int u, int x) // 在节点 u 的子树中获取小于 x 的权值数量
    {
        int c = 0;
        while (u)
            if (x > p[u].x)
            {
                c += p[u].c;
                if (!p[u].r || x < p[p[u].r].x) u = p[u].l;
                else c += p[p[u].l].sz, u = p[u].r;
            }
            else return c;
        return c;
    }
    int getkthat(int u, int k) // 获取节点 u 的子树中第 k 小的权值
    {
        while (u)
            if (k > p[u].c)
            {
                k -= p[u].c;
                if (k <= p[p[u].l].sz) u = p[u].l;
                else k -= p[p[u].l].sz, u = p[u].r;
            }
            else return p[u].x;
        return -1;
    }
};

:::

当然，以上的代码无法通过任何需要使用平衡树的题目，只要构造一套插入单调递增序列的数据，其单次操作的时间复杂度就会达到 \mathcal{O}(n)。

所以，我们需要某种方法，使得这棵树的高度维持在 \log n 级别。

然而，在这颗树上做旋转等操作来维护平衡似乎是困难的，因为要满足前序遍历序列单调递增，转一转就会彻底乱掉。我真的能在满足那些性质的情况下做旋转维持平衡吗？这真的可能吗？

答案是显然的，如果这颗平衡树造不出来就没有这篇文章了。没错，我将使用最通俗易懂的语言，最不花里胡哨的描述，告诉你，不能。

呃呃，既然不能旋转，我们只能开发一种新的平衡维护方式了，这正好还满足了我们对这颗平衡树猎奇程度的需求。

如果在树中有一条由 \{1, 2, 3\} 组成的右链，可以通过将 2 设为 1 的左子节点，3 设为 1 的右子节点来降低树高。

我们来看如下两个例子：

:::align{center}

:::

观察，可以发现我们可以通过将右子节点带着自己的左子树，插入到左子节点一侧，来降低树高。

但是这样基于树高的平衡似乎过于严格，在我们的树上很难实现。于是如果设每个节点的左右子树的大小分别为 sz_l, sz_r，我们维持 \max(sz_l, sz_r) \le 2 \cdot \min(sz_l, sz_r) + 1。

接下来，再来看下一个例子：

:::align{center}

:::

现在是左子节点超重了，如果采用之前的方式平衡，我们只能把节点 6 插到 1 和 7 之间，变成这样：

:::align{center}

:::

节点 2 失衡了，这我无疑是愤怒的。然而并不知道如何优化。于是我们先实现代码：

:::info[代码] 注意到上述这些操作中节点飞来飞去，我也不知道到底在干什么，于是将其命名为 fold。

struct tree
{
private:
    int tl, rt;
    struct node { int x, c, sz, l, r; } p[1100006];
    inline void pushup(int u)
    {
        p[u].sz = p[u].c + p[p[u].l].sz + p[p[u].r].sz;
    }
    inline int setnode(int x, int c)
    {
        int u = ++tl;
        p[u].x = x, p[u].c = p[u].sz = c;
        return u;
    }
    int buildat(const vector<pair<int, int>>& x, int l, int r)
    {
        if (l >= r) return 0;
        int u = setnode(x[l].first, x[l].second);
        if (l + 1 < r)
        {
            p[u].l = buildat(x, l + 1, l + r >> 1);
            p[u].r = buildat(x, l + r >> 1, r);
            pushup(u);
        }
        return u;
    }
    void insertnd(int& u, int v)
    {
        if (!v) return;
        if (!u) { u = v; return; }
        if (!p[u].r) p[u].r = v;
        else insertnd(p[u].r, v);
        pushup(u), fold(u);
    }
    void erasend(int& u)
    {
        if (!p[u].l) { u = p[u].r; return; }
        if (!p[u].r) { u = p[u].l; return; }
        p[u].x = p[p[u].l].x, p[u].c = p[p[u].l].c, erasend(p[u].l);
        pushup(u), fold(u);
    }
    void insertat(int& u, int x, int c)
    {
        if (!u) { u = setnode(x, c); return; }
        if (x == p[u].x) { p[u].c += c, p[u].sz += c; return; }
        if (x < p[u].x) swap(x, p[u].x), swap(c, p[u].c);
        if (p[u].r && x >= p[p[u].r].x) insertat(p[u].r, x, c);
        else insertat(p[u].l, x, c);
        pushup(u), fold(u);
    }
    void eraseat(int& u, int x)
    {
        if (!u) return;
        if (x == p[u].x && p[u].c > 1) { p[u].c--, p[u].sz--; return; }
        if (x == p[u].x) { erasend(u); return; }
        if (p[u].r && x >= p[p[u].r].x) eraseat(p[u].r, x);
        else eraseat(p[u].l, x);
        pushup(u), fold(u);
    }
    int countlat(int u, int x)
    {
        int c = 0;
        while (u)
            if (x > p[u].x)
            {
                c += p[u].c;
                if (!p[u].r || x < p[p[u].r].x) u = p[u].l;
                else c += p[p[u].l].sz, u = p[u].r;
            }
            else return c;
        return c;
    }
    int getkthat(int u, int k)
    {
        while (u)
            if (k > p[u].c)
            {
                k -= p[u].c;
                if (k <= p[p[u].l].sz) u = p[u].l;
                else k -= p[p[u].l].sz, u = p[u].r;
            }
            else return p[u].x;
        return -1;
    }
    void fold(int& u)
    {
        if (!u) return;
        if (p[p[u].r].sz > (p[p[u].l].sz << 1) + 1 && (p[p[u].r].l || p[p[u].r].r))
        {
            int v = p[u].r;
            if (p[v].l && !p[v].r) swap(p[v].l, p[v].r);
            int w = p[v].r;
            p[v].r = 0, pushup(v), insertnd(p[u].l, v), p[u].r = w, pushup(u);
            return;
        }
        if (p[p[u].l].sz > (p[p[u].r].sz << 1) + 1 && (p[p[u].l].l || p[p[u].l].r))
        {
            int v = p[u].l;
            if (p[v].l && !p[v].r) swap(p[v].l, p[v].r);
            int w = p[v].r;
            p[v].r = 0, pushup(v), insertnd(w, p[u].r), p[u].r = w, pushup(u);
            return;
        }
    }
public:
    inline void build(const vector<pair<int, int>>& x) { rt = buildat(x, 0, x.size()); }
    inline void insert(int x) { insertat(rt, x, 1); }
    inline void erase(int x) { eraseat(rt, x); }
    inline int kth(int k) { return getkthat(rt, k); }
    inline int rnk(int x) { return countlat(rt, x) + 1; }
    inline int prv(int x) { return getkthat(rt, countlat(rt, x)); }
    inline int nxt(int x) { return getkthat(rt, countlat(rt, x + 1) + 1); }
};

:::

提交到 P6316。欸？怎么过了？而且速度还不错，无快读版本总用时 11 秒多。然而有一个点非常慢，明显被卡了。

目前有比较明显的缺陷。思考，发现可以让节点 2 收养其左子节点的的右子树，来让树稍微再平衡一点。在刚才的例子中，树则是变成了这样：

:::align{center}

:::

经测试似乎单次操作最坏复杂度大约为 \mathcal{O}(\log^2 n)，似乎每次操作均摊复杂度大约为 \mathcal{O}(\log n)。很废物对吧。

关于复杂度嘛……具体为什么我也不清楚，我实测构造的数据是这么告诉我的。如果您有 hack，欢迎来卡。或者如果有对于时间复杂度的分析，也欢迎给出。

:::info[代码]

struct ft // Folding Tree designed by Gary0
{
private:
    int tl, rt;
    struct node { int x, c, sz, l, r; } p[1100006];
    inline void pushup(int u)
    {
        p[u].sz = p[u].c + p[p[u].l].sz + p[p[u].r].sz;
    }
    inline int setnode(int x, int c)
    {
        int u = ++tl;
        p[u].x = x, p[u].c = p[u].sz = c;
        return u;
    }
    int buildat(const vector<pair<int, int>>& x, int l, int r)
    {
        if (l >= r) return 0;
        int u = setnode(x[l].first, x[l].second);
        if (l + 1 < r)
        {
            p[u].l = buildat(x, l + 1, l + r >> 1);
            p[u].r = buildat(x, l + r >> 1, r);
            pushup(u);
        }
        return u;
    }
    void insertnd(int& u, int v)
    {
        if (!v) return;
        if (!u) { u = v; return; }
        if (!p[u].r) p[u].r = v;
        else insertnd(p[u].r, v);
        pushup(u), fold(u);
    }
    void erasend(int& u)
    {
        if (!p[u].l) { u = p[u].r; return; }
        if (!p[u].r) { u = p[u].l; return; }
        p[u].x = p[p[u].l].x, p[u].c = p[p[u].l].c, erasend(p[u].l);
        pushup(u), fold(u);
    }
    void insertat(int& u, int x, int c)
    {
        if (!u) { u = setnode(x, c); return; }
        if (x == p[u].x) { p[u].c += c, p[u].sz += c; return; }
        if (x < p[u].x) swap(x, p[u].x), swap(c, p[u].c);
        if (p[u].r && x >= p[p[u].r].x) insertat(p[u].r, x, c);
        else insertat(p[u].l, x, c);
        pushup(u), fold(u);
    }
    void eraseat(int& u, int x)
    {
        if (!u) return;
        if (x == p[u].x && p[u].c > 1) { p[u].c--, p[u].sz--; return; }
        if (x == p[u].x) { erasend(u); return; }
        if (p[u].r && x >= p[p[u].r].x) eraseat(p[u].r, x);
        else eraseat(p[u].l, x);
        pushup(u), fold(u);
    }
    int countlat(int u, int x)
    {
        int c = 0;
        while (u)
            if (x > p[u].x)
            {
                c += p[u].c;
                if (!p[u].r || x < p[p[u].r].x) u = p[u].l;
                else c += p[p[u].l].sz, u = p[u].r;
            }
            else return c;
        return c;
    }
    int getkthat(int u, int k)
    {
        while (u)
            if (k > p[u].c)
            {
                k -= p[u].c;
                if (k <= p[p[u].l].sz) u = p[u].l;
                else k -= p[p[u].l].sz, u = p[u].r;
            }
            else return p[u].x;
        return -1;
    }
    void fold(int& u)
    {
        if (!u) return;
        if (p[p[u].r].sz > (p[p[u].l].sz << 1) + 1 && (p[p[u].r].l || p[p[u].r].r))
        {
            int v = p[u].r;
            if (p[v].l && !p[v].r) swap(p[v].l, p[v].r);
            int w = p[v].r;
            if (p[p[v].l].sz >= 2)
            {
                int vl = p[v].l;
                if (p[vl].l && !p[vl].r) swap(p[vl].l, p[vl].r);
                int tp = p[vl].r;
                p[vl].r = 0, pushup(vl), p[v].r = tp, pushup(v);
            }
            else p[v].r = 0, pushup(v);
            insertnd(p[u].l, v), p[u].r = w, pushup(u);
            return;
        }
        if (p[p[u].l].sz > (p[p[u].r].sz << 1) + 1 && (p[p[u].l].l || p[p[u].l].r))
        {
            int v = p[u].l;
            if (p[v].l && !p[v].r) swap(p[v].l, p[v].r);
            int w = p[v].r;
            if (p[p[v].l].sz >= 2)
            {
                int vl = p[v].l;
                if (p[vl].l && !p[vl].r) swap(p[vl].l, p[vl].r);
                int tp = p[vl].r;
                p[vl].r = 0, pushup(vl), p[v].r = tp, pushup(v);
            }
            else p[v].r = 0, pushup(v);
            insertnd(w, p[u].r), p[u].r = w, pushup(u);
            return;
        }
    }
public:
    inline void build(const vector<pair<int, int>>& x) { rt = buildat(x, 0, x.size()); }
    inline void insert(int x) { insertat(rt, x, 1); }
    inline void erase(int x) { eraseat(rt, x); }
    inline int kth(int k) { return getkthat(rt, k); }
    inline int rnk(int x) { return countlat(rt, x) + 1; }
    inline int prv(int x) { return getkthat(rt, countlat(rt, x)); }
    inline int nxt(int x) { return getkthat(rt, countlat(rt, x + 1) + 1); }
};

:::

测试一（P6136 【模板】普通平衡树（数据加强版））：

• 线性建树 - 总用时 9.90s，最慢点 797ms。
• 线性建树 + 快读 - 总用时 7.56s，最慢点 683ms。

可以注意到这个东西在一般数据下性能还算优秀，精细实现可以与红黑树媲美（实测的带快读红黑树跑了 7.88s，最慢点 797ms）。

为了搞这个东西交了一百多发 P6136，不算滥用评测资源吧。？

测试二（Library Checker）：

• 线性建树 + 快读快写 - 最慢点 183ms。

感谢 @EternalAlexander 的 OI Painter，本文中所有图片使用 OI Painter Beta 1.3 制作。

:::info[gpt-5.2-high 关于复杂度的分析] 不保证有价值，仅供参考。

0. 计时模型

把“基本代价”定义为：一次对结点指针 u 的访问并执行常数次整数运算/比较（例如一次 while 循环体、一次递归帧内除递归调用外的语句）。则总运行时间与“访问结点次数”只差一个与输入无关的常数倍，下面只证明访问结点次数的上界。

令任意时刻多重集合元素总数（含重复）为

1. 平衡条件与高度上界（只用到代码中的判定）

定义对结点 u 的性质 P(u)：

• 若 u.r 是非叶结点（即 p[u].r 存在且它有至少一个孩子），则必须有 \mathrm{sz}(u.r)\le 2\,\mathrm{sz}(u.l)+1;
• 若 u.l 是非叶结点，则必须有 \mathrm{sz}(u.l)\le 2\,\mathrm{sz}(u.r)+1.

注意这正是 fold(u) 的两个 if 的否定（fold 只在“更重的一侧是非叶结点”时触发），因此：

引理 1（fold 的后置条件）
对任意结点引用 fold(u) 返回后，性质 P(u) 成立。

证明：fold 的两段代码分别覆盖 P(u) 的两条约束被违反的情形；若违反且重子为非叶则进入分支并做重构后 return，从而保证返回时该违反情形已被消除；若未进入任何分支，则两条约束本来就成立。证毕。

由 P(u) 推出“规模收缩”：

引理 2（收缩不等式）
若 P(u) 成立，且 u 的某个孩子 v\in\{u.l,u.r\} 是非叶结点，则

证明： 不妨 v=u.r 为非叶。由 P(u)：\mathrm{sz}(u.r)\le 2\,\mathrm{sz}(u.l)+1。令

引理 2（结构合法性的强归纳）

命题： 对 insertat、eraseat、insertnd 的任一次调用，若调用前： （i）唯一被修改的是从调用入口到某个叶子的单一路径； （ii）该路径之外悬挂的所有子树均已合法；

则调用返回后，该次调用所作用的整棵（子）树合法。

证明（对最终子树规模 s=\mathrm{sz}(u) 强归纳）：

• 基础情形 s\le 1：无子节点，WB2 平凡成立。

• 归纳步： 假设命题对所有规模 <s 的调用成立。考察规模为 s 的调用：函数体恰好递归进入一个子节点（insertat/eraseat 按比较结果二选一；insertnd 固定递归进入 p[u].r），该子节点子树规模 <s。由归纳假设，该子调用返回后其整个子树合法；另一子树按条件 (ii) 已合法。故此刻只有 u 自身可能违反 WB2。

  随后执行 pushup(u); fold(u)：

  • 若 u 满足 WB2，fold 为空操作，整棵子树合法，命题成立。
  • 若不满足（设右重），由引理 1，w,v' 规模均为 \Theta(\mathrm{sz}(u.r))<s，且 v' 作为独立合法子树（裁剪过程只动 v 内部单一路径，其余部分未动，仍合法，可同样由归纳假设验证）传入 insertnd(p[u].l, v')。此调用的总规模 \mathrm{sz}(u.l)+\mathrm{sz}(v')<s（w 与 u 本身已被排除），满足条件 (i)(ii)，由归纳假设，该调用返回后新 u.l 整体合法——这正是对"u.l 会否残留不平衡"的回答：不会，因为 insertnd 自身在回溯时对其递归路径上的每一层都调用了 pushup+fold，而这些调用同样被本归纳覆盖。

  令 u.r:=w（合法，规模 \Theta(\mathrm{sz}(u.r))），由引理 1 的比例关系 \mathrm{sz}(\text{新}\,u.l)=\Theta(\mathrm{sz}(u.r))=\mathrm{sz}(w)（同阶），代入 WB2 定义中的常数核验（即标准的单/双旋正确性数值校验，与经典 BB[2] 树旋转证明一致）可得 u 自身此时也满足 WB2。

  综上，整棵以 u 为根的子树合法。\blacksquare

结论： 任一 insert/erase 调用之后，整棵树始终合法。子树失衡的隐患已被 insertnd 自身嵌入的逐层 fold 调用，通过同一归纳过程消解。

3. 深度引理

引理 3： 合法树中任意节点的子节点规模 <\tfrac23 乘以父节点规模；故合法树高度 h=O(\log_{3/2} N)，其中 N 为树中元素总数。

证明： 设 u 两子规模 s_l\le s_r，WB2 给出 s_r\le 2s_l+1，故

由引理 3，countlat、getkthat 以及 insert/erase 的主路径代价均为 O(\log N)。

4. 嵌套级联的总代价：势能论证

由引理 2 的证明可见，一次顶层 insert/erase 可能引发多层嵌套的 fold→insertnd→fold→…。需证明：无论嵌套多深，总代价仍为 O(\log N) 摊还。

定义势能

引理 4（级联代价的摊还界）： 一次顶层操作所引发的全部（含任意嵌套深度的）fold 触发之和，其实际工作量之和 \le C\cdot(\Phi_{\text{前}}-\Phi_{\text{后}})+O(1)，其中 C 为常数。

证明要点：

• 每一次未触发的 fold 调用只做 O(1) 判断，沿任意一条调用链（无论是最外层 insertat 的主路径，还是某次 insertnd 内部的下降路径）此类调用的条数由引理 3 保证为 O(\log(\text{该子树规模}))，而由引理 1 规模呈几何衰减（每次嵌套的子问题规模至少缩小常数倍 \Theta(\mathrm{sz}(u))\to\Theta(\mathrm{sz}(u.r))，且触发条件要求 \mathrm{sz}(u.r)>2\mathrm{sz}(u.l)+1，故挂起子问题的规模严格小于原问题的某个固定比例），故各层嵌套的"非触发遍历"总代价构成公比 <1 的几何级数，和为 O(\log N)。
• 每一次触发的 fold，由引理 1，其产生的 w（规模 \Theta(\mathrm{sz}(v))）被提升一层（远离深层、靠近 u），而被合并入 u.l 的 v' 规模同阶，这一重排使得"规模大的子树更靠近根"，依 \Phi 定义（规模越大、层数越浅，\log(\mathrm{sz}) 之和越小——因子树规模总和守恒而嵌套深度减小），可验证该次触发导致 \Phi 严格下降至少一个与规模无关的正常数 \delta>0。故触发次数之和 \le \Phi_{\text{前}}/\delta，相应代价之和 \le C\cdot(\Phi_{\text{前}}-\Phi_{\text{后}})。\blacksquare

推论（单次操作摊还代价）：

对 t=1,\dots,m 求和，势能项 telescope：

其中 \Phi_0\le n\log_{3/2}(n+1)=O(n\log n) 来自初始 build（buildat 本身是中点递归建树，不调用 fold，代价线性 O(n)，但其势能作为后续级联代价的初始账单上界为 O(n\log n)）。

5. 总复杂度

• 读入：O(n+m)
• 排序：O(n\log n)
• 去重 + buildat：O(n)
• m$ 次操作（含任意深度级联，由引理 4 摊还）：$O\big(m\log(n+m)+n\log n\big)

时间复杂度（总量，摊还）：

空间复杂度： 节点总数 \le 初始去重节点数 + 至多 m 次 insert 新建节点数 =O(n+m)，对应数组 p[1100006]：

结论