Heap
可持久化可并堆一般用于求解
如果一种可并堆的时间复杂度不是均摊的,那么它在可持久化后单次操作的时间复杂度就保证是
可持久化左偏树¶
在学习本内容前,请先了解 左偏树 的相关内容。
回顾左偏树的合并过程,假设我们要合并分别以
-
如果
x,y x+y -
选择
x,y -
递归合并
x y x -
维护当前合并后左偏树的左偏性质,维护
dist
值,返回选择的根节点。
由于每次递归都会使 dist[x]+dist[y]
减少一,而 dist[x]
是
可持久化要求保留历史信息,使得之后能够访问之前的版本。要将左偏树可持久化,就要将其沿途修改的路径复制一遍。
所以可持久化左偏树的合并过程是这样的:
-
如果
x,y x+y -
选择
x,y p -
递归合并
p y p -
维护以
p dist
值,返回p
由于左偏树一次最多只会修改并新建
参考实现¶
int merge(int x, int y) {
if (!x || !y) return x + y;
if (v[x] > v[y]) swap(x, y);
int p = ++cnt;
lc[p] = lc[x];
v[p] = v[x];
rc[p] = merge(rc[x], y);
if (dist[lc[p]] < dist[rc[p]]) swap(lc[p], rc[p]);
dist[p] = dist[rc[p]] + 1;
return p;
}
buildLast update and/or translate time of this article,Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.