1442 字
7 分钟
可持久化左偏树

1. 回顾左偏树的合并过程#

假设我们要合并分别以 x,yx, y 为根节点的两棵左偏树,且维护的左偏树满足小根堆的性质:

  1. 若为空则返回:如果 x,yx, y 中有结点为空,返回 x+yx + y。
  2. 确定根节点:选择 x,yx, y 两结点中权值更小的结点,作为合并后左偏树的根。
  3. 递归合并:递归合并 xx 的右子树与 yy,将合并后的根节点作为 xx 的右儿子。
  4. 维护性质:维护当前合并后左偏树的左偏性质,维护 dist 值,返回选择的根节点。

时间复杂度分析#

由于每次递归都会使 dist[x] + dist[y] 减少一,而 dist[x] 是 O(log⁡n)O(\log n) 的,一次最多只会修改 O(log⁡n)O(\log n) 个结点,所以这样操作的时间复杂度是 O(log⁡n)O(\log n)。


2. 可持久化左偏树#

可持久化要求保留历史信息,使得之后能够访问之前的版本。要将左偏树可持久化,就要将其沿途修改的路径复制一遍(路径复制)。

可持久化合并过程#

  1. 若为空则返回:如果 x,yx, y 中有结点为空,返回 x+yx + y。
  2. 新建副本:选择 x,yx, y 两结点中权值更小的结点,新建该结点的一个复制 pp,作为合并后左偏树的根。
  3. 递归合并:递归合并 pp 的右子树与 yy,将合并后的根节点作为 pp 的右儿子。
  4. 维护性质:维护以 pp 为根的左偏树的左偏性质,维护其 dist 值,返回 pp。

复杂度分析#

  • 空间与时间复杂度:由于左偏树一次合并最多只会修改并新建 O(log⁡n)O(\log n) 个结点,设操作次数为 mm,则可持久化左偏树的时间复杂度和空间复杂度均为 O(mlog⁡n)O(m \log n)。

复制于OIWIKI


P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院

原始的A*算法为,我们对于每条路径,先后扩展之后都按照估价函数压入优先队列中,会发现其中许多路径具有重叠部分,每次扩展都会再次被压入,极大浪费了空间和时间,因此我们将问题进行一个转化. 考虑一个任意一条从起点s到t的一条路径,这条路径一定是经过若干最短路树上的边和非最短路树上的边,显然如果全走最短路树上的边一定是最短路,同时任意两点之间也一定存在一条非最短路树上的路径(树上的路径唯一性),形式化的,一条任意路径可以由一个边序列如下描述: e1,e2,e3…eke_1,e_2,e_3\dots e_k

 s.t.\text{ s.t.}

  • eie_i不在最短路上
  • ∀i\forall i,ei=(ui,vi)e_i=(u_i,v_i),ei+1=(ui+1,vi+1)e_{i+1}=(u_{i+1},v_{i+1}),ui+1u_{i+1}在最短路树上是uiu_i的祖先 我们令δ(ei)=wei−(dis(u)−dis(v))\delta (e_i)=w_{e_i}-(dis(u)-dis(v)),那么这条路径的长度len=∑δ(ei)len=\sum\delta(e_i) 我们在每个结点都开一个堆,存储从这个结点出发的所有非最短路上的边,在堆内按照δ\delta排序,那么对于当前的序列e1,e2,e3…eke_1,e_2,e_3\dots e_k,我们有两种扩展方式:
  • 移动到vkv_k所在堆并取出最大元素 ek+1e_{k+1} ,序列变成e1,e2,e3…ek,ek+1e_1,e_2,e_3\dots e_k,e_{k+1}
  • 将当前序列的末尾元素替换,已知当前序列在vk−1v_{k-1}所在堆,继续取出更大的非树边替换掉末尾元素,序列变成e1,e2,e3…ek′e_1,e_2,e_3\dots e'_k 能保证不重不漏的扩展出所有状态.

代码

#include <bits/stdc++.h>
#include <queue>
#include <utility>
#define ll long long
#define N 4000005
#define MAX 5005
#define inf 2e12
#define pr pair<ll, int>
using namespace std;
ll k, n, q, m, ans;
ll E;
class mergeable_heap {
public:
struct node {
ll val = 0;
int ls = 0, rs = 0, dis = 0, pos = 0;
} tr[N];
int id = 0;
mergeable_heap() { tr[0] = {0, 0, 0, -1, 0}; }
int new_(pr x) {
tr[++id].val = x.first;
tr[id].pos = x.second; // 注意不要++两次
return id;
}
int clone(int x) {
tr[++id] = tr[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);
x = clone(x);
rc = merge(rc, y);
if (tr[lc].dis < tr[rc].dis)
swap(lc, rc);
tr[x].dis = tr[rc].dis + 1;
return x;
}
int del(int x) { return merge(lc, rc); }
auto get_val(int x) { return tr[x].val; }
#undef lc
#undef rc
} mh;
vector<vector<tuple<int, ll, int>>> rev_map1;
vector<vector<tuple<int, ll, int>>> map1;
vector<int> pre;
vector<int> root;
vector<ll> dis;
vector<tuple<int, int, ll>> edges;
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
long double ee;
cin >> n >> m >> ee;
E = (ll)(ee * (10000.0) + 0.5);
rev_map1.assign(n + 5, {});
map1.assign(n + 5, {});
dis.assign(n + 5, inf);
root.assign(n + 5, 0);
pre.assign(n + 5, -1);
for (int i = 1; i <= m; i++) {
ll a, b, c;
long double cc;
cin >> a >> b >> cc;
c = (ll)(cc * (10000.0) + 0.5);
edges.push_back({a, b, c});
rev_map1[b].push_back({a, c, edges.size() - 1});
map1[a].push_back({b, c, edges.size() - 1});
}
auto dij = [&](int st) {
vector<bool> vis(n + 5, 0);
priority_queue<pr> q;
q.push({0, st});
dis[st] = 0;
while (q.size()) {
auto [_, x] = q.top();
q.pop();
if (vis[x])
continue;
vis[x] = 1;
for (auto [v, w, id] : rev_map1[x]) {
if (dis[v] > dis[x] + w) {
dis[v] = dis[x] + w;
pre[v] = id;
q.push({-dis[v], v});
}
}
}
};
dij(n);
vector<ll> s;
for (int i = 1; i <= n; i++)
s.push_back(i);
sort(s.begin(), s.end(), [&](int x, int y) { return dis[x] < dis[y]; });
auto build = [&]() {
for (auto now : s) {
if (dis[now] >= inf || now == n)
continue; // 很重要!!改了半天才发现这里的问题,到达n之后就不需要再往祖先走了
if (pre[now] != -1) {
int from = get<1>(edges[pre[now]]);
root[now] = root[from];
}
for (auto [v, w, id] : map1[now]) {
if (id == pre[now])
continue;
root[now] = mh.merge(root[now], mh.new_({w - dis[now] + dis[v], id}));
}
}
};
build();
#define lc mh.tr[rt]
.ls
#define rc mh.tr[rt]
.rs auto astar = [&](int st) {
priority_queue<pr> q;
if (dis[st] < inf && E >= dis[st]) {
E -= dis[st];
ans++;
if (root[st])
q.push({-(dis[st] + mh.get_val(root[st])), root[st]});
}
while (q.size()) {
auto [cost, rt] = q.top();
cost = -cost;
q.pop();
if (cost > E)
break;
E -= cost;
ans++;
if (lc) {
q.push({-(cost - mh.get_val(rt) + mh.get_val(lc)), lc});
}
if (rc) {
q.push({-(cost - mh.get_val(rt) + mh.get_val(rc)), rc});
}
int v = get<1>(edges[mh.tr[rt].pos]);
if (root[v]) {
q.push({-(cost + mh.get_val(root[v])), root[v]});
}
}
};
astar(1);
cout << ans;
return 0;
}
可持久化左偏树
https://sanzenin.top/posts/obsidian/可持久化左偏树/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

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

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取