1382 字
7 分钟
左偏树 可并堆

左偏树 可并堆#

左偏树是一种具有左偏性质的堆有序的二叉树。注意,左偏树不是二叉堆。

左偏树的每一个节点存储的信息包括左右子节点 lc[x],rc[x]lc[x], rc[x]、权值 v[x]v[x] 和 距离 dis[x]dis[x]。

左儿子或右儿子为空的节点,称为外节点。节点的距离的定义:即该节点到与其最近的外节点经过的边数。

我们规定,外节点的距离为 0,空节点的距离为 -1。


[图片缺失:Pasted image 20260114153201.png]*左偏树实例

左偏树的性质#

  • 性质1:堆的性质,对于任意节点 v[x]≤v[lc[x]],v[rc[x]]v[x] \le v[lc[x]], v[rc[x]] (小根堆)。
  • 性质2:左偏性质,左儿子的距离 ≥\ge 右儿子的距离,dis[lc]≥dis[rc]dis[lc] \ge dis[rc]。
  • 性质3:任意节点的距离 = 其右儿子的距离 + 1,dis[x]=dis[rc]+1dis[x] = dis[rc] + 1。
  • 性质4:一棵有 nn 个节点的二叉树,根的 dis≤log⁡(n+1)−1dis \le \log(n+1) - 1。

性质4 的证明推导#

因为根的距离为 xx 的二叉树至少有 x+1x+1 层是满二叉树,那么至少有 2x+1−12^{x+1} - 1 个节点。

即 n≥2x+1−1n \ge 2^{x+1} - 1,所以 x≤log⁡(n+1)−1x \le \log(n+1) - 1。

合并操作 (Merge)#

合并操作是左偏树最重要的操作,过程主要包含两个维度的维护:

  1. 维护堆的性质: 先取值较小的那个根作为合并后的堆的根节点,然后递归合并其右儿子与另一个堆,作为合并后的堆的右儿子。
  2. 维护左偏性质: 合并后若左儿子的 disdis 小于右儿子的 disdis(即 dis[lc]<dis[rc]dis[lc] < dis[rc]),就交换两个儿子。

时间复杂度分析#

由于左偏性质,每递归一层,其中一个堆根节点的 disdis 就会减小 1。

而一棵有 nn 个节点的二叉树,根的 dis<log⁡(n+1)dis < \log(n+1)。

所以合并两个大小分别为 nn 和 mm 的堆的时间复杂度是 O(log⁡n+log⁡m)O(\log n + \log m)。


P3377 【模板】可并堆 1 代码

#include <bits/stdc++.h>
#include <cstdlib>
#include <utility>
#define ll long long
#define N 100005
#define pr pair<ll, ll>
using namespace std;
ll k, n, m;
class dsu {
public:
int fa[N];
void init() {
for (int i = 1; i <= N; i++)
fa[i] = i;
}
int find(int x) { return fa[x] = (fa[x] == x ? x : find(fa[x])); }
bool merge(int x, int y) {
int rx, ry;
rx = find(x);
ry = find(y);
if (rx == ry)
return 0;
fa[rx] = ry;
return 1;
}
} ds;
class mergeable_heap {
public:
int val[N], rc[N], lc[N], dis[N], id = 0;
int new_(int x) {
val[++id] = x;
return id;
}
int merge(int x, int y) {
if (!x || !y)
return x + y;
if (make_pair(val[x], x) > make_pair(val[y], y))
swap(x, y);
rc[x] = merge(rc[x], y);
if (dis[rc[x]] > dis[lc[x]])
swap(lc[x], rc[x]);
dis[x] = dis[rc[x]] + 1;
return x;
}
} mh;
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
ds.init();
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
mh.new_(x);
}
mh.val[0] = -1; // 可能会合并到空节点
while (m--) {
ll opt, x, y;
cin >> opt;
if (opt == 1) {
cin >> x >> y;
if (mh.val[x] == -1 || mh.val[y] == -1)
continue;
x = ds.find(x), y = ds.find(y);
if (x != y)
ds.fa[x] = ds.fa[y] = mh.merge(ds.find(x), ds.find(y));
} else {
cin >> x;
if (mh.val[x] == -1)
cout << -1 << '\n';
else {
x = ds.find(x); // 注意要判断的是这个点有无被删除,而不是这个点的祖先
cout << mh.val[x] << '\n';
mh.val[x] = -1;
ds.fa[x] = ds.fa[mh.lc[x]] = ds.fa[mh.rc[x]] = mh.merge(mh.lc[x], mh.rc[x]);
}
}
}
return 0;
}

P1552 [APIO2012] 派遣

#include <bits/stdc++.h>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#define ll long long
#define N 200005
#define M 2005
#define pr pair<ll, ll>
using namespace std;
ll n, m, ans;
class mergeable_heap {
public:
struct node {
ll ls = 0, rs = 0, siz = 1, val = 0, sum = 0, dis = 0;
} tr[N];
int root[N];
mergeable_heap() {
tr[0].dis = -1;
tr[0].siz = 0;
}
int id = 0;
int new_(int x) {
tr[++id] = {0, 0, 1, x, x};
return id;
}
#define lc tr[x]
.ls
#define rc tr[x]
.rs int
merge(int x, int y) {
if (!x || !y)
return x + y;
if (make_pair(tr[x].val, x) < make_pair(tr[y].val, y))
swap(x, y);
rc = merge(rc, y);
if (tr[lc].dis < tr[rc].dis)
swap(lc, rc);
tr[x].dis = tr[rc].dis + 1;
tr[x].siz = tr[lc].siz + tr[rc].siz + 1, tr[x].sum = tr[lc].sum + tr[rc].sum + tr[x].val;
return x;
}
int del(int x) {
int tem = merge(lc, rc);
return tem;
}
} mheap;
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
vector<ll> fa(n + 5, 0);
vector<ll> pay(n + 5, 0);
vector<ll> lead(n + 5, 0);
vector<ll> root(n + 5, 0);
for (int i = 1; i <= n; i++) {
cin >> fa[i] >> pay[i] >> lead[i];
root[i] = mheap.new_(pay[i]);
}
for (int i = n; i >= 1; i--) {
while (mheap.tr[root[i]].sum > m) {
root[i] = mheap.del(root[i]);
}
ans = max(ans, lead[i] * mheap.tr[root[i]].siz);
int fa_ = fa[i];
if (fa_)
root[fa_] = mheap.merge(root[fa_], root[i]);
}
cout << ans;
return 0;
}

P4331 [BalticOI 2004] Sequence (Day1)

#include <bits/stdc++.h>
#include <cstdlib>
#include <utility>
#define ll long long
#define N 1000005
#define pr pair<ll, ll>
using namespace std;
ll n, ans, m, cnt;
vector<ll> a;
class mergeable_heap {
public:
struct node {
int siz = 1, dis = 0, ls = 0, rs = 0, num = 0;
} tr[N];
int id = 0;
mergeable_heap() {
tr[0].dis = -1;
tr[0].siz = 0;
}
int new_(int x) {
tr[++id].num = x;
return id;
}
#define lc tr[x]
.ls
#define rc tr[x]
.rs int
merge(int x, int y) {
if (!x || !y)
return x + y;
if (make_pair(a[tr[x].num], x) < make_pair(a[tr[y].num], y))
swap(x, y);
rc = merge(rc, y);
if (tr[lc].dis < tr[rc].dis)
swap(lc, rc);
tr[x].dis = tr[rc].dis + 1, tr[x].siz = tr[lc].siz + tr[rc].siz + 1;
return x;
}
int del(int x) {
int tem = merge(lc, rc);
return tem;
}
int size(int x) { return tr[x].siz; }
} mh;
struct segment {
int l, r, rt;
} s[N];
int top;
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
a.assign(n + 5, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] -= i;
}
for (int i = 1; i <= n; i++) {
s[++top] = {i, i, mh.new_(i)};
while (top > 1 && a[mh.tr[s[top - 1].rt].num] > a[mh.tr[s[top].rt].num]) {
s[top - 1].rt = mh.merge(s[top - 1].rt, s[top].rt);
s[top - 1].r = s[top].r;
top--;
while (mh.size(s[top].rt) > (s[top].r - s[top].l + 1) / 2 + 1) {
s[top].rt = mh.del(s[top].rt);
}
}
}
vector<ll> ans;
ll tol = 0;
for (int i = 1; i <= top; i++) {
for (int j = s[i].l; j <= s[i].r; j++) {
ans.push_back(a[mh.tr[s[i].rt].num] + j);
tol += abs(a[j] - a[mh.tr[s[i].rt].num]);
}
}
cout << tol << '\n';
for (auto now : ans)
cout << now << '\n';
return 0;
}

左偏树 可并堆
https://sanzenin.top/posts/obsidian/左偏树/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取