persistent_dsu.hpp¶
Fully persistent union-find. Union by size keeps every parent chain logarithmic, while a path-copying segment tree stores the parent-or-size array. Versions share all untouched segment-tree nodes, so any old version can be queried or branched from after later merges.
Verified by persistent_unionfind.
查询并查集在任意历史版本中的连通关系，并从旧版本继续合并；适合版本树上的动态连通性。
Implementation¶
#ifndef NOYA_PERSISTENT_DSU_HPP
#define NOYA_PERSISTENT_DSU_HPP 1
/// @complexity Time: O(log^2 n) per leader, same, size, or merge query.
/// Space: O(log n) new nodes per successful merge and O(1) per version copy.
#include <cassert>
#include <memory>
#include <utility>
#include <vector>
namespace noya {
/// @brief Fully persistent union-find. Union by size keeps every parent chain
/// logarithmic, while a path-copying segment tree stores the parent-or-size
/// array. Versions share all untouched segment-tree nodes, so any old version
/// can be queried or branched from after later merges.
class persistent_dsu {
struct node {
int left = 0;
int right = 0;
int value = -1;
};
struct storage {
std::vector<node> nodes{{}};
int get(int root, int low, int high, int position) const {
if (root == 0) {
return -1;
}
if (high - low == 1) {
return nodes[root].value;
}
int middle = low + (high - low) / 2;
if (position < middle) {
return get(nodes[root].left, low, middle, position);
}
return get(nodes[root].right, middle, high, position);
}
int set(int root, int low, int high, int position, int value) {
int current = int(nodes.size());
nodes.push_back(nodes[root]);
if (high - low == 1) {
nodes[current].value = value;
return current;
}
int middle = low + (high - low) / 2;
if (position < middle) {
nodes[current].left =
set(nodes[root].left, low, middle, position, value);
} else {
nodes[current].right =
set(nodes[root].right, middle, high, position, value);
}
return current;
}
};
int count_ = 0;
int root_ = 0;
std::shared_ptr<storage> data_;
persistent_dsu(int count, int root, std::shared_ptr<storage> data)
: count_(count), root_(root), data_(std::move(data)) {}
int value(int position) const {
assert(data_ && 0 <= position && position < count_);
return data_->get(root_, 0, count_, position);
}
public:
persistent_dsu() = default;
explicit persistent_dsu(int count)
: count_(count), data_(std::make_shared<storage>()) {
assert(count > 0);
}
/// @brief Return the representative of vertex in this version.
int leader(int vertex) const {
int parent = value(vertex);
while (parent >= 0) {
vertex = parent;
parent = value(vertex);
}
return vertex;
}
bool same(int first, int second) const {
return leader(first) == leader(second);
}
int size(int vertex) const { return -value(leader(vertex)); }
/// @brief Return a new version in which the two components are united.
persistent_dsu merge(int first, int second) const {
first = leader(first);
second = leader(second);
if (first == second) {
return *this;
}
int first_size = -value(first);
int second_size = -value(second);
if (first_size < second_size) {
std::swap(first, second);
std::swap(first_size, second_size);
}
int next_root =
data_->set(root_, 0, count_, first, -(first_size + second_size));
next_root = data_->set(next_root, 0, count_, second, first);
return persistent_dsu(count_, next_root, data_);
}
};
} // namespace noya
#endif // NOYA_PERSISTENT_DSU_HPP
#include <cassert>
#include <memory>
#include <utility>
#include <vector>
/// @complexity Time: O(log^2 n) per leader, same, size, or merge query.
/// Space: O(log n) new nodes per successful merge and O(1) per version copy.
namespace noya {
/// @brief Fully persistent union-find. Union by size keeps every parent chain
/// logarithmic, while a path-copying segment tree stores the parent-or-size
/// array. Versions share all untouched segment-tree nodes, so any old version
/// can be queried or branched from after later merges.
class persistent_dsu {
struct node {
int left = 0;
int right = 0;
int value = -1;
};
struct storage {
std::vector<node> nodes{{}};
int get(int root, int low, int high, int position) const {
if (root == 0) {
return -1;
}
if (high - low == 1) {
return nodes[root].value;
}
int middle = low + (high - low) / 2;
if (position < middle) {
return get(nodes[root].left, low, middle, position);
}
return get(nodes[root].right, middle, high, position);
}
int set(int root, int low, int high, int position, int value) {
int current = int(nodes.size());
nodes.push_back(nodes[root]);
if (high - low == 1) {
nodes[current].value = value;
return current;
}
int middle = low + (high - low) / 2;
if (position < middle) {
nodes[current].left =
set(nodes[root].left, low, middle, position, value);
} else {
nodes[current].right =
set(nodes[root].right, middle, high, position, value);
}
return current;
}
};
int count_ = 0;
int root_ = 0;
std::shared_ptr<storage> data_;
persistent_dsu(int count, int root, std::shared_ptr<storage> data)
: count_(count), root_(root), data_(std::move(data)) {}
int value(int position) const {
assert(data_ && 0 <= position && position < count_);
return data_->get(root_, 0, count_, position);
}
public:
persistent_dsu() = default;
explicit persistent_dsu(int count)
: count_(count), data_(std::make_shared<storage>()) {
assert(count > 0);
}
/// @brief Return the representative of vertex in this version.
int leader(int vertex) const {
int parent = value(vertex);
while (parent >= 0) {
vertex = parent;
parent = value(vertex);
}
return vertex;
}
bool same(int first, int second) const {
return leader(first) == leader(second);
}
int size(int vertex) const { return -value(leader(vertex)); }
/// @brief Return a new version in which the two components are united.
persistent_dsu merge(int first, int second) const {
first = leader(first);
second = leader(second);
if (first == second) {
return *this;
}
int first_size = -value(first);
int second_size = -value(second);
if (first_size < second_size) {
std::swap(first, second);
std::swap(first_size, second_size);
}
int next_root =
data_->set(root_, 0, count_, first, -(first_size + second_size));
next_root = data_->set(next_root, 0, count_, second, first);
return persistent_dsu(count_, next_root, data_);
}
};
} // namespace noya