Persistent Array
(data-structure/persistent-array.hpp)

• View this file on GitHub
• Last update: 2026-06-28 15:22:40+09:00
• Include: #include "data-structure/persistent-array.hpp"

永続配列．

長さ $N$ の列 $A=(A_0,A_1,\dots,A_{N-1})$ を管理し，更新前の状態を保存して後から戻せるようにする．

• build(v)：列 v で初期化する．
• get(k)：$A_k$ を取得する．
• mutable_get(k)：$A_k$ へのポインタを取得する．必要な頂点だけコピーされるため，値を代入すると新しい状態が作られる．
• take_snapshot()：現在の状態を保存し，その番号を返す．
• apply_snapshot(k)：take_snapshot で保存した状態 k に戻す．

内部では添字を $B$ 進数で見た trie を永続化している． 各操作でコピーされる頂点数は $O(\log_B N)$ 個．

Required by

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

Verified with

• verify/union-find/LC_persistent_unionfind.test.cpp

Code

#pragma once

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 "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
 */

Back to top page