左偏树

本文转载（或修改）自 OI-Wiki

什么是左偏树？

左偏树 是一种 可并堆，具有堆的性质，并且可以快速合并。

左偏树的定义和性质

对于一棵二叉树，我们定义 外节点 为子节点数小于两个的节点，定义一个节点的 \(\mathrm{dist}\) 为其到子树中最近的外节点所经过的边的数量。空节点的 \(\mathrm{dist}\) 为 \(0\)。

注意

有些资料中对 \(\mathrm{dist}\) 的定义是本文中的 \(\mathrm{dist}\) 减 \(1\)，这样定义是因为代码编写时可以省略一些判空流程，但需要注意应预先置空节点的 \(\mathrm{dist}\) 为 \(-1\)。本文中所有代码对 \(\mathrm{dist}\) 的定义 均为后者，请注意与行文间 \(\mathrm{dist}\) 定义的差别。

左偏树是一棵二叉树，它不仅具有堆的性质，并且是「左偏」的：每个节点左儿子的 \(\mathrm{dist}\) 都大于等于右儿子的 \(\mathrm{dist}\)。

因此，左偏树每个节点的 \(\mathrm{dist}\) 都等于其右儿子的 \(\mathrm{dist}\) 加一。

需要注意的是，\(\mathrm{dist}\) 不是深度，左偏树的深度没有保证，一条向左的链也符合左偏树的定义。

核心操作：合并（merge）

合并两个堆时，由于要满足堆性质，先取值较小（为了方便，本文讨论小根堆）的那个根作为合并后堆的根节点，然后将这个根的左儿子作为合并后堆的左儿子，递归地合并其右儿子与另一个堆，作为合并后的堆的右儿子。为了满足左偏性质，合并后若左儿子的 \(\mathrm{dist}\) 小于右儿子的 \(\mathrm{dist}\)，就交换两个儿子。

参考代码：

实现

int merge(int x, int y)
{
    if (!x || !y) return x | y;
    if (val[y] < val[x]) swap(x, y);
    rs[x] = merge(rs[x], y);
    if (dist[ls[x]] < dist[rs[x]]) swap(ls[x], rs[x]);
    dist[x] = dist[rs[x]] + 1;
    return x;
}

由于左偏性质，每递归一层，其中一个堆根节点的 \(\mathrm{dist}\) 就会减小 \(1\)，而一棵有 \(n\) 个节点的二叉树，根的 \(\mathrm{dist}\) 不超过 \(\left\lceil\log (n+1)\right\rceil\)，所以合并两个大小分别为 \(n\) 和 \(m\) 的堆复杂度是 \(O(\log n+\log m)\)。

关于 \(\mathrm{dist}\) 性质的证明

一棵根的 \(\mathrm{dist}\) 为 \(x\) 的二叉树至少有 \(x-1\) 层是满二叉树，那么就至少有 \(2^x-1\) 个节点。注意这个性质是所有二叉树都具有的，并不是左偏树所特有的。

左偏树的其它操作

插入节点

单个节点也可以视为一个堆，合并即可。

删除根

合并根的左右儿子即可。

删除任意节点

做法

先将左右儿子合并，然后自底向上更新 \(\mathrm{dist}\)、不满足左偏性质时交换左右儿子，当 \(\mathrm{dist}\) 无需更新时结束递归即可。

复杂度证明

先考虑 merge 的过程，每次都会使 \(x\) 或 \(y\) 向下一层，也就是说最极端的情况，就是一直选择左偏树的右节点（\(\mathrm{dist}\) 最小的节点）向下一层，此时 \(\mathrm{dist}\) 减少了 \(1\)。

再考虑 pu 的过程，我们令当前 pu 的这个节点为 \(x\)，其父亲为 \(y\)，一个节点的「初始 \(\mathrm{dist}\) 」为它在 pu 前的 \(\mathrm{dist}\)。从被删除节点的父亲开始递归，有两种情况：

\(x\) 是 \(y\) 的右儿子，此时 \(y\) 的初始 \(\mathrm{dist}\) 为 \(x\) 的初始 \(\mathrm{dist}\) 加一。
\(x\) 是 \(y\) 的左儿子，由于节点的 \(\mathrm{dist}\) 最多减一，因此只有 \(y\) 的左右儿子初始 \(\mathrm{dist}\) 相等时（此时左儿子 \(\mathrm{dist}\) 减一会导致左右儿子互换）才会继续递归下去，因此 \(y\) 的初始 \(\mathrm{dist}\) 仍然是 \(x\) 的初始 \(\mathrm{dist}\) 加一。

所以，我们得到，每递归一层 \(x\) 的初始 \(\mathrm{dist}\) 就会加一，因此最多递归 \(O(\log n)\) 层。

模板题目的代码如下：

P3377 【模板】左偏树/可并堆

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MAXN = 100010;
int n, m, op, x, y;
int ls[MAXN], rs[MAXN], dist[MAXN], rt[MAXN];
bitset<MAXN> deled;
struct node
{
    int id, val;
    bool operator<(node x) const { return val == x.val ? id < x.id : val < x.val; }
} val[MAXN];
int getf(int x) { return rt[x] == x ? x : rt[x] = getf(rt[x]); }
int merge(int x, int y)
{
    if (!x || !y) return x | y;
    if (val[y] < val[x]) swap(x, y);
    rs[x] = merge(rs[x], y);
    if (dist[ls[x]] < dist[rs[x]]) swap(ls[x], rs[x]);
    dist[x] = dist[rs[x]] + 1;
    return x;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> val[i].val, rt[i] = i, val[i].id = i;
    while (m--)
    {
        cin >> op >> x;
        if (op == 1)
        {
            cin >> y;
            if (deled[x] || deled[y]) continue;
            x = getf(x);
            y = getf(y);
            if (x != y) rt[x] = rt[y] = merge(x, y);
        }
        if (op == 2)
        {
            if (deled[x])
            {
                cout << -1 << endl;
                continue;
            }
            x = getf(x);
            cout << val[x].val << endl;
            deled[x] = true;
            rt[ls[x]] = rt[rs[x]] = rt[x] = merge(ls[x], rs[x]);
            ls[x] = rs[x] = dist[x] = 0;
        }
    }
    return 0;
}

整个堆加上/减去一个值、乘上一个正数

其实可以打标记且不改变相对大小的操作都可以。

类似线段树的做法，在根打上标记，删除根/合并堆（访问儿子）时下传标记即可：

实现

void addtag(int x, int v);
void pd(int x);
void pu(int x);
int mergeWithTag(int x, int y)
{
    if (!x || !y) return x | y;
    pd(x);
    if (val[y] < val[x]) swap(x, y);
    rs[x] = mergeWithTag(rs[x], y);
    if (dist[ls[x]] < dist[rs[x]]) swap(ls[x], rs[x]);
    pu(x);
    dist[x] = dist[rs[x]] + 1;
    return x;
}
int pop(int x) { return pd(x), pu(x = mergeWithTag(ls[x], rs[x])), x; }

具体的看题目去。