左偏树

摘要：左偏树，左偏树，左偏树

左偏树（Leftist Tree）是一种 可并堆，具有堆的性质，能在 $O(\log n)$ 的时间内进行合并。

再讲左偏树之前，要先引入 $\mathrm{dist}$ 的定义以及性质：

对于一棵二叉树，我们定义 外节点 为左儿子或右儿子为空的节点；
定义一个外节点的 $\mathrm{dist}$ 为 $0$，一个不是外节点的节点 $\mathrm{dist}$ 为其到子树中最近的外节点的距离加一。空节点的 $\mathrm{dist}$ 为 $-1$。

左偏树 之所以是「左偏」的，是因为每个节点左儿子的 $\mathrm{dist}$ 都大于等于右儿子的 $\mathrm{dist}$。

进而我们可以归纳出左偏树的性质：

$\mathrm{val}[i]\le \mathrm{val}[son[i]]$
$\mathrm{dist}[lson]\ge\mathrm{dist}[rson]$
$\mathrm{dist}[x]=\mathrm{dist}[rson]+1$

为了保证你建出来的是一颗左偏树，需要加上 tre[0].dist = -1。

我们的印象中，平衡树是具有非常小的深度的，这也意味着到达任何一个节点所经过的边数很少。左偏树并不是为了快速访问所有的节点而设计的，它的目的是快速访问最小节点以及在对树修改后快速的恢复堆性质。

从图中我们可以看到它并不平衡，由于性质 2 的缘故，它的结构偏向左侧，不过距离的概念和树的深度并不同，左偏树并不意味着左子树的节点数或是深度一定大于右子树。

基本操作

合并（merge）

定义 merge(x,y) 为合并两棵分别以 $x,y$ 为根节点的左偏树，其返回值为合并之后的根节点。

合并两个堆时，由于要满足堆性质，先取值较小的那个根作为合并后堆的根节点（小根堆），然后将这个根的左儿子作为合并后堆的左儿子，递归地合并其右儿子与另一个堆，作为合并后的堆的右儿子。

为了满足左偏性质，合并后若左儿子的 $\mathrm{dist}$ 小于右儿子的 $\mathrm{dist}$，就交换两个儿子。

// 象征性地放一下代码
int merge(int x, int y) {
    if (!x || !y)
        return x | y;
    if (tre[x].val > tre[y].val)
        swap(x, y);
    tre[x].rs = merge(tre[x].rs, y);
    if (tre[tre[x].rs].dist > tre[tre[x].ls].dist) 
        swap(tre[x].ls, tre[x].rs);
    tre[tre[x].ls].root = tre[tre[x].rs].root = tre[x].root = x;
    tre[x].dist = tre[tre[x].rs].dist + 1;
    return x;
}

插入

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

查询（find）

前面说过左偏树的深度没有保证，那就不能简单的跳父亲，

想一想并查集是怎么维护的，记录每个结点的父亲，类比过来，记录每个节点的 root，然后路径压缩即可。

记得初始化。

删除（pop）

删除根的话合并左右儿子即可。

void pop(int x) {
    tre[x].val = -1;
    tre[tre[x].ls].root = tre[x].ls;
    tre[tre[x].rs].root = tre[x].rs;
    tre[x].root =  merge(tre[x].ls, tre[x].rs);
}

删除任意节点就比较麻烦，你得让它六亲不认，，，但也可以在 merge() 时 push_up()，自底向上更新 $\mathrm{dist}$，这是一种比较简便的写法。

void push_up(int x) {
    if (!x) return;
    if (tre[x].dist != tre[tre[x].ls].dist + 1) {
        tre[x].dist =  tre[tre[x].rs].dist + 1;
        push_up(tre[x].root);
    }
}

int merge(int x, int y) {
    // ...
    push_up(x);
    return x;
}

void pop(int x) {
    tre[x].val = -1;
    tre[x].root =  merge(tre[x].ls, tre[x].rs);
}

修改（change_val）

第一想法是：pop() -> tre[x].val = c -> merge()，

没问题，但 pop() 中一定要删掉指向儿子节点的边，不然父亲指向儿子，儿子指向父亲，，，爆栈 MLE，

一般情况下父节点指向它的边不用删，例如：

void change_val(int x, llt b) {
    tre[x].val -= (tre[x].val > b ? b : tre[x].val);
    int ll = tre[tre[x].ls].root = tre[x].ls; tre[x].ls = 0;
    int rr = tre[tre[x].rs].root = tre[x].rs; tre[x].rs = 0;
    merge(get(x), merge(ll, rr));
}

需要注意的是上面这个问题中维护的是一个大根堆，x 的 val 改变之后还是比父节点小的，所以这么写是没问题的。

具体的写法要看题目里要求的是大根堆还是小根堆，change_val 之后 val 变大还是变小，要根据题面灵活变换的。

树上问题

以 P3261 [JLOI2015]城池攻占为例：

$n$ 座城池构成树形结构，$m$ 个骑士 fighting，因为问题涉及合并，所以考虑左偏树，

开始时 $m$ 个骑士各自构成一个堆，然后合并到初始城池，top[i] 记录第 $i$ 城池的堆顶元素；然后 DFS，先统计一遍 dep（我们可以根据 dep 统计出骑士攻占的城池数目），再把在这座城池牺牲的骑士弹出去，统计答案，剩下的向上一级合并，然后就成功了。

void dfs(int x) {
    for (int i = head[x]; i; i = e[i].nxt) {
        int y = e[i].v;
        dep[y] = dep[x] + 1;
        dfs(y);
    }
    while (top[x] && tre[top[x]].val < h[x]) {
        ans1[x]++;
        ans2[top[x]] = dep[c[top[x]]] - dep[x];
        top[x] = pop(top[x]);
    } 
    change(a[x], top[x], v[x]);
    if (x != 1)
        top[fa[x]] = merge(top[x], top[fa[x]]);
    else {
        while (top[x]) {
            ans2[top[x]] = dep[c[top[x]]] + 1;
            top[x] = pop(top[x]);
        }
    }
}

Tag 标记

还是上面这个题，骑士的战斗力会发生变化，乘或者加，你想到了什么，线段树2 ！

与线段树类似，我们也可以打 tag，push_down，先乘后加，成功了。

void change(int opt, int x, llt val) {
    if (opt) {
        tre[x].val *= val;
        tre[x].add *= val;
        tre[x].mul *= val;
    }
    else {
        tre[x].val += val;
        tre[x].add += val;
    }
}

void push_down(int x) {
    change(1, tre[x].ls, tre[x].mul);
    change(0, tre[x].ls, tre[x].add);
    change(1, tre[x].rs, tre[x].mul);
    change(0, tre[x].rs, tre[x].add);
    tre[x].mul = 1;
    tre[x].add = 0;
}

shu 学问题

看一道例题：

P4331 [BalticOI 2004]Sequence 数字序列

给定一个序列 $a_1, a_2, ··· , a_n$，求出一个严格递增序列 $b_1 < b_2 < ··· < b_n$，使得 $\sum_{i=1}^{n}|a_i - b_i|$ 最小。

Solution I

我们先考虑原题的弱化版：

求不下降序列 $b$ 使得 $\sum_{i=1}^n|a_i-b_i|$最小，我们可以感性的得到两个结论：

若原序列 $a$ 满足 $a_1<a_2<\dots<a_n$，显然最优情况为 $b_i=a_i$
若原序列 $a$ 满足 $a_1>a_2>\dots>a_n$，显然最优情况为 $b_{i}=a_{mid}$

有了上述的两种情况再去想整个序列，$a$ 序列是由一些单调区间组成，因此我们可以将原序列 $a$ 拆成若干个单调区间，最后再将答案合并。

将两个堆合并来找中位数，不难想到用左偏树。

假设我们已经找到前 $k$ 个数的最优解，队列中有 $cnt$ 段区间，每段区间最优解为 $w_1,w_2,…,w_{cnt}$，现在要加入 $a_{k+1}$，并更新队列。

首先把 $a_{k+1}$ 加入队尾，令 $w_{cnt+1}=a_{k+1}$，如果 $w_{cnt}>w_{cnt+1}$，就将最后两个区间合并，并找出新区间的最优解。重复上述过程，直至满足 $w$ 单调递增。

算法中涉及到以下两种操作：合并两个有序集以及查询某个有序集内的中位数。能较高效地支持这两种操作的数据结构有不少，一个比较明显的例子是二叉检索树（BST），它的询问操作复杂度是 $O(\log n)$，但合并操作不甚理想，采用启发式合并，总时间复杂度为 $O(n\log^2n)$。

我们发现，只有当某一区间内的中位数比后一区间内的中位数大时，合并操作才会发生，也就是说，任一区间与后面的区间合并后，该区间内的中位数不会变大。于是我们可以用大根堆来维护每个区间内的中位数，当堆中的元素大于该区间内元素的一半时，删除堆顶元素，这样堆中的元素始终为区间内较小的一半元素，堆顶元素即为该区间内的中位数。考虑到我们必须高效地完成合并操作，左偏树是一个理想的选择。左偏树的询问操作时间复杂度为 $O(1)$，删除和合并操作时间复杂度都是 $O(\log n)$，而询问操作和合并操作少于 $n$ 次，删除操作不超过 $n/2$ 次（因为删除操作只会在合并两个元素个数为奇数的堆时发生），因此用左偏树实现，可以把算法的时间复杂度降为 $O(n\log n)$。

再考虑原题面：题目要求的是一个递增序列 $b$，可以用减下标来实现（即输入时把每个数都减去对应下标，输出时加上），这样就可以将递增序列转化成不下降序列，这样就可以保证每一段区间的序列 $b$ 不一样了（原本有很多连续一段区间全是中位数，不能保证递增）。

Solution II

首先是一个显然的 DP。

$f[i][j]$ 表示前 $i$ 个数字，其中最后一个数字小于等于 $j$ 的最优答案

考虑转移，首先让 $f[i][j] = f[i-1][j] + \left|a[i] - j\right|$

然后再让 $f[i][j] = \min(f[i][j],f[i][j-1])$

如果我们得到这个 dp 数组，用一般的方法就可以倒着推回去得到方案。

其实 $f[i][j]$ 其实是一个斜率单调以 $1$ 递减的折线。我们只需要知道拐点就可以了。

考虑加入一个绝对值函数，如果在之前斜率为 $0$ 的直线上，相当于这个左边斜率减一，否则相当于右边的斜率都加一（这时候斜率为为 $-1$ 的就没了，和右边并起来了）。

我们用堆来维护折线的拐点的横坐标即可。

扩展

P3273 [SCOI2011]棘手的操作

U x y: 加一条边，连接第x个节点和第y个节点
A1 x v: 将第x个节点的权值增加v
A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v
A3 v: 将所有节点的权值都增加v
F1 x: 输出第x个节点当前的权值
F2 x: 输出第x个节点所在的连通块中，权值最大的节点的权值
F3: 输出所有节点中，权值最大的节点的权值

~~这道题的正解不是左偏树，但 OI wiki 上有这个题就加上了~~

首先，找一个节点所在堆的堆顶要用并查集，而不能暴力向上跳。

再考虑单点查询，若用普通的方法打标记，就得查询点到根路径上的标记之和，最坏情况下可以达到的复杂度。如果只有堆顶有标记，就可以快速地查询了，但如何做到呢？

可以用类似启发式合并的方式，每次合并的时候把较小的那个堆标记暴力下传到每个节点，然后把较大的堆的标记作为合并后的堆的标记。由于合并后有另一个堆的标记，所以较小的堆下传标记时要下传其标记减去另一个堆的标记。由于每个节点每被合并一次所在堆的大小至少乘二，所以每个节点最多被下放次标记，暴力下放标记的总复杂度就是。

再考虑单点加，先删除，再更新，最后插入即可。

然后是全局最大值，可以用一个平衡树/支持删除任意节点的堆（如左偏树）/multiset 来维护每个堆的堆顶。

所以，每个操作分别如下：