Persistent Potentialized Union Find
(union-find/persistent-potentialized-union-find.hpp)

• View this file on GitHub
• Last update: 2026-06-28 15:41:08+09:00
• Include: #include "union-find/persistent-potentialized-union-find.hpp"

永続ポテンシャル付き Union Find．

通常の Union Find の連結性に加えて，各頂点 $v$ に値 $p_v$ があるとして差分の情報を管理する． 各状態を snapshot として保存し，あとから過去の状態に戻せる．

PersistentPotentializedUnionFind<G> として使う． G は value_type, op(x,y), e(), inv(x) を持つ群を表す型． 加法の場合は AddGroup<T> を使えばよい．

• find(v)：頂点 $v$ を含む連結成分の代表頂点を返す．
• size(v)：頂点 $v$ を含む連結成分の頂点数を返す．
• same(u, v)：頂点 $u,v$ が同じ連結成分に含まれるかを返す．
• diff(u, v)：$p_u-p_v$ に対応する値を返す．
• unite(u, v, w)：$p_u-p_v=w$ という制約を追加する．既存の情報と矛盾しないかを返す．
• take_snapshot()：現在の状態を保存し，その番号を返す．
• apply_snapshot(k)：保存した状態 k に戻す．

永続化には PersistentArray を用いているため，path compression は行わない． 各操作の時間計算量は木の高さと永続配列の更新に依存する．

Depends on

• algebraic-structure/group.hpp
• algebraic-structure/magma.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp
• Persistent Array (data-structure/persistent-array.hpp)

Code

#pragma once

#include "data-structure/persistent-array.hpp"
#include "algebraic-structure/group.hpp"

template <class G>
REQUIRES(Group<G>)
struct PersistentPotentializedUnionFind {
  using T = typename G::value_type;

 private:
  PersistentArray<int, 8> a;
  PersistentArray<T, 8> p;

 public:
  PersistentPotentializedUnionFind(int n) {
    a.build(vector<int>(n, -1));
    p.build(vector<T>(n, G::e()));
  }
  int find(int x) { return a.get(x) < 0 ? x : find(a.get(x)); }
  T pot(int x) {
    int y = a.get(x);
    return y < 0 ? p.get(x) : G::op(p.get(x), pot(y));
  }
  T diff(int x, int y) { return G::op(pot(x), G::inv(pot(y))); }
  int size(int x) { return -a.get(find(x)); }
  bool same(int x, int y) { return find(x) == find(y); }
  // pot(u) - pot(v) = w
  // return : consistent
  bool unite(int u, int v, T w) {
    int x = find(u), y = find(v);
    if (x == y) return diff(u, v) == w;
    w = G::op(G::op(w, G::inv(pot(u))), pot(v));
    auto ax = a.get(x);
    auto ay = a.get(y);
    if (ax < ay) {
      *p.mutable_get(y) = G::op(p.get(x), G::inv(w));
      *a.mutable_get(x) += ay;
      *a.mutable_get(y) = x;
    } else {
      *p.mutable_get(x) = G::op(p.get(y), w);
      *a.mutable_get(y) += ax;
      *a.mutable_get(x) = y;
    }
    return true;
  }
  int take_snapshot() {
    a.take_snapshot();
    return p.take_snapshot();
  }
  void apply_snapshot(int k) {
    a.apply_snapshot(k);
    p.apply_snapshot(k);
  }
};
/**
 * @brief Persistent Potentialized Union Find
 * @docs docs/union-find/persistent-potentialized-union-find.md
 */

#line 2 "union-find/persistent-potentialized-union-find.hpp"

#line 2 "data-structure/persistent-array.hpp"

template <class T, int B = 8>
struct PersistentArray {
  struct Node {
    T val;
    Node* child[B] = {};
    Node() {}
    Node(const T& v) : val(v) {}
  };
  Node* root;
  vector<Node*> snapshots;
  PersistentArray() : root(nullptr) {}
  T get(Node* t, int k) { return k == 0 ? t->val : get(t->child[k % B], k / B); }
  T get(const int& k) { return get(root, k); }
  pair<Node*, T*> mutable_get(Node* t, int k) {
    t = t ? new Node(*t) : new Node();
    if (k == 0) return {t, &t->val};
    auto p = mutable_get(t->child[k % B], k / B);
    t->child[k % B] = p.first;
    return {t, p.second};
  }
  T* mutable_get(const int& k) {
    auto ret = mutable_get(root, k);
    root = ret.first;
    return ret.second;
  }
  Node* build(Node* t, const T& val, int k) {
    if (!t) t = new Node();
    if (k == 0) {
      t->val = val;
      return t;
    }
    t->child[k % B] = build(t->child[k % B], val, k / B);
    return t;
  }
  void build(const vector<T>& v) {
    root = nullptr;
    for (int i = 0; i < v.size(); i++) root = build(root, v[i], i);
  }
  int take_snapshot() {
    snapshots.push_back(root);
    return snapshots.size() - 1;
  }
  void apply_snapshot(int k) {
    root = snapshots[k];
  }
};

/**
 * @brief Persistent Array
 * @docs docs/val-structure/persistent-array.md
 */
#line 2 "algebraic-structure/util.hpp"
#ifdef __cpp_concepts
#define REQUIRES(...) requires __VA_ARGS__
#else
#define REQUIRES(...)
#endif
#line 3 "algebraic-structure/magma.hpp"

#ifdef __cpp_concepts
template <class M>
concept Magma = requires(typename M::value_type x, typename M::value_type y) {
  typename M::value_type;
  { M::op(x, y) } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMagma {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
};
template <class T>
struct MulMagma {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
};
template <class T, T id>
struct MaxMagma {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
};
template <class T, T id>
struct MinMagma {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
};
#line 3 "algebraic-structure/monoid.hpp"

#ifdef __cpp_concepts
template <class M>
concept Monoid = Magma<M> && requires {
  { M::e() } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMonoid {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
};
template <class T>
struct MulMonoid {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
};
template <class T, T id>
struct MaxMonoid {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
  static T e() { return id; }
};
template <class T, T id>
struct MinMonoid {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
  static T e() { return id; }
};
#line 3 "algebraic-structure/group.hpp"

#ifdef __cpp_concepts
template <class G>
concept Group = Monoid<G> && requires(typename G::value_type x) {
  { G::inv(x) } -> same_as<typename G::value_type>;
};
#endif

template <class T>
struct AddGroup {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
  static T inv(T x) { return -x; }
};
template <class T>
struct MulGroup {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
  static T inv(T x) { return T(1) / x; }
};
#line 5 "union-find/persistent-potentialized-union-find.hpp"

template <class G>
REQUIRES(Group<G>)
struct PersistentPotentializedUnionFind {
  using T = typename G::value_type;

 private:
  PersistentArray<int, 8> a;
  PersistentArray<T, 8> p;

 public:
  PersistentPotentializedUnionFind(int n) {
    a.build(vector<int>(n, -1));
    p.build(vector<T>(n, G::e()));
  }
  int find(int x) { return a.get(x) < 0 ? x : find(a.get(x)); }
  T pot(int x) {
    int y = a.get(x);
    return y < 0 ? p.get(x) : G::op(p.get(x), pot(y));
  }
  T diff(int x, int y) { return G::op(pot(x), G::inv(pot(y))); }
  int size(int x) { return -a.get(find(x)); }
  bool same(int x, int y) { return find(x) == find(y); }
  // pot(u) - pot(v) = w
  // return : consistent
  bool unite(int u, int v, T w) {
    int x = find(u), y = find(v);
    if (x == y) return diff(u, v) == w;
    w = G::op(G::op(w, G::inv(pot(u))), pot(v));
    auto ax = a.get(x);
    auto ay = a.get(y);
    if (ax < ay) {
      *p.mutable_get(y) = G::op(p.get(x), G::inv(w));
      *a.mutable_get(x) += ay;
      *a.mutable_get(y) = x;
    } else {
      *p.mutable_get(x) = G::op(p.get(y), w);
      *a.mutable_get(y) += ax;
      *a.mutable_get(x) = y;
    }
    return true;
  }
  int take_snapshot() {
    a.take_snapshot();
    return p.take_snapshot();
  }
  void apply_snapshot(int k) {
    a.apply_snapshot(k);
    p.apply_snapshot(k);
  }
};
/**
 * @brief Persistent Potentialized Union Find
 * @docs docs/union-find/persistent-potentialized-union-find.md
 */

Back to top page