永続配列 (src/DataStructure/PersistentArray.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-09-21 21:45:32+09:00
• Include: #include "src/DataStructure/PersistentArray.hpp"

M分木

計算量

get: $O(\log_M N)$
at: $O(M \log_M N)$

Required by

• Union-Find(完全永続) (src/DataStructure/UnionFind_Persistent.hpp)

Verified with

• test/atcoder/abc133_f.PerArr.test.cpp
• test/yosupo/persistent_unionfind.test.cpp

Code

#pragma once
#include <vector>
template <class T, size_t M= 8> class PersistentArray {
 struct Node {
  T val;
  Node *ch[M];
 } *root;
 T get(Node *t, size_t k) const { return t ? (k ? get(t->ch[(k - 1) % M], (k - 1) / M) : t->val) : T(); }
 bool is_null(Node *t, size_t k) const { return t ? (k ? is_null(t->ch[(k - 1) % M], (k - 1) / M) : false) : true; }
 template <bool persistent= true> T &at(Node *&t, size_t k) {
  if (!t) t= new Node();
  else if constexpr (persistent) t= new Node(*t);
  return k ? at<persistent>(t->ch[(k - 1) % M], (k - 1) / M) : t->val;
 }
public:
 PersistentArray(): root(nullptr) {}
 PersistentArray(size_t n, T v): root(nullptr) {
  for (size_t i= n; i--;) at<false>(root, i)= v;
 }
 PersistentArray(T *bg, T *ed): root(nullptr) {
  for (size_t i= ed - bg; i--;) at<false>(root, i)= *(bg + i);
 }
 PersistentArray(const std::vector<T> &ar): PersistentArray(ar.data(), ar.data() + ar.size()) {}
 bool is_null(size_t k) const { return is_null(root, k); }
 T get(size_t k) const { return get(root, k); }
 T &at(size_t k) { return at<true>(root, k); }
 T &operator[](size_t k) { return at(k); }
 T operator[](size_t k) const { return get(k); }
};

#line 2 "src/DataStructure/PersistentArray.hpp"
#include <vector>
template <class T, size_t M= 8> class PersistentArray {
 struct Node {
  T val;
  Node *ch[M];
 } *root;
 T get(Node *t, size_t k) const { return t ? (k ? get(t->ch[(k - 1) % M], (k - 1) / M) : t->val) : T(); }
 bool is_null(Node *t, size_t k) const { return t ? (k ? is_null(t->ch[(k - 1) % M], (k - 1) / M) : false) : true; }
 template <bool persistent= true> T &at(Node *&t, size_t k) {
  if (!t) t= new Node();
  else if constexpr (persistent) t= new Node(*t);
  return k ? at<persistent>(t->ch[(k - 1) % M], (k - 1) / M) : t->val;
 }
public:
 PersistentArray(): root(nullptr) {}
 PersistentArray(size_t n, T v): root(nullptr) {
  for (size_t i= n; i--;) at<false>(root, i)= v;
 }
 PersistentArray(T *bg, T *ed): root(nullptr) {
  for (size_t i= ed - bg; i--;) at<false>(root, i)= *(bg + i);
 }
 PersistentArray(const std::vector<T> &ar): PersistentArray(ar.data(), ar.data() + ar.size()) {}
 bool is_null(size_t k) const { return is_null(root, k); }
 T get(size_t k) const { return get(root, k); }
 T &at(size_t k) { return at<true>(root, k); }
 T &operator[](size_t k) { return at(k); }
 T operator[](size_t k) const { return get(k); }
};

Back to top page