做网站营销怎么去推广,手机编程的app,公司logo设计大全 图片欣赏,dedecms 一键更新网站可持久化并查集
可持久化并查集 按秩合并并查集 可持久化数组
首先并查集不能采用路径压缩#xff0c;这是因为一次findR操作中#xff0c;fa数组的很多位置#xff08;u-ru#xff09;会发生修改#xff0c;由于每次修改都需要在可持久化数组上复制产生log个新结…可持久化并查集
可持久化并查集 按秩合并并查集 可持久化数组
首先并查集不能采用路径压缩这是因为一次findR操作中fa数组的很多位置u-ru会发生修改由于每次修改都需要在可持久化数组上复制产生log个新结点空间复杂度过大。我们不希望每个版本的fa数组的差别太大最好只有常数个位置改变。 启发式合并/按秩合并
当 merge(u,v) 时找到ru,rv后让 sz 小的接在sz大的下面
if(sz[ru] sz[rv]) swap(ru,rv);
fa[ru] rv;
sz[rv] sz[ru]或者让高度到叶子的最长距离height 小的接在 height 大的下面
if(height[ru] height[rv]) swap(ru,rv);
fa[ru] rv;
if(height[ru] height[rv]) height[rv];按sz合并一般称为启发式合并按height合并一般称为按秩合并二者的复杂度都是logN每向上走1条边身处的子树sz至少扩大1倍且每次 merge 操作时fa数组只有2个位置会发生修改(fa[ru]和sz[rv])直接用可持久化下标线段树维护fa数组就可以实现可持久化。 空间复杂度是O(NlogN) 时间复杂度是O(Nlog2NNlog^2NNlog2N)
例题
P3402 可持久化并查集 「NOI2018」归程
