左偏树是一类拥有下列操作的数据结构：
-
插入一个数 \(O(log n)\)
-
求最小值 \(O(1)\)
-
删除一个节点 \(O(log n)\)
-
合并两棵树 \(O(log n)\)
左偏树本身具有堆的性质，又称为可并堆。
以维护最小值为例：
概念：
-
权值\(val\)
-
距离\(dis\)：到最近的根节点的距离 （\(\leqslant log n\)）
\(left\rightarrow dist\rightarrow right\rightarrow dist\)
\(f[k]\)：距离为\(k\)的子树，至少包含多少个点。
- \(f[k]\geqslant 2^k-1\)
证明：\(k=1,n=k-1\)
\(n=k, f(n)\geqslant 2^{k-1}-1+2^{k-1}-1+1=2^k-1\)
故必须要有\(f[k]\geqslant 2^k-1\)
\(merge(a,b)\)：合并子树\(a,b\)，并返回合并后的根节点。
比较\(a,b\)的根节点的大小，如果\(a\)的根节点小于\(b\)的根节点，则把\(b\)插到\(a\)的右子树，然后检查\(a\)是否符合左偏性质，如果不满足就把左右子树交换。
这个操作存\(root\)时需要路径压缩。
为什么可以用并查集？ 只有合并而没有分裂。
于是下面的操作就很简单了。
插入操作：建立只包含一个点的左偏树，将其与原树合并。
最小值：根节点
删除操作：合并左右子树。
code
bool cmp(int x, int y)
{
if (v[x] != v[y]) return v[x] < v[y];
return x < y;
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int merge(int x, int y)
{
if (!x || !y) return x + y;
if (cmp(y, x)) swap(x, y);
r[x] = merge(r[x], y);
if (dist[r[x]] > dist[l[x]]) swap(l[x], r[x]);
dist[x] = dist[r[x]] + 1;
return x;
}
习题选做：
P4359 【CQOI2016】 伪光滑数
P3261 【JLOI2015】 城池攻占