test/unittest/persistent-array.test.cpp

• View this file on GitHub
• Last update: 2026-08-04 11:55:02+00:00

Depends on

• Persistent Array (structure/others/persistent-array.hpp)

Code

// competitive-verifier: STANDALONE

#include "../../structure/others/persistent-array.hpp"

#include <cassert>
#include <vector>

int main() {
  PersistentArray<int, 2> original;
  original.build(std::vector<int>{10, 20, 30, 40, 50});
  assert(original.get(0) == 10);
  assert(original.get(4) == 50);

  auto first = original;
  *first.mutable_get(1) = 200;
  *first.mutable_get(4) = 500;
  assert(original.get(1) == 20);
  assert(original.get(4) == 50);
  assert(first.get(1) == 200);
  assert(first.get(4) == 500);

  auto second = first;
  *second.mutable_get(0) = -1;
  assert(first.get(0) == 10);
  assert(second.get(0) == -1);
}

#line 1 "test/unittest/persistent-array.test.cpp"
// competitive-verifier: STANDALONE

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

#include <utility>
#include <vector>

template <typename T, int LOG>
struct PersistentArray {
  struct Node {
    T data;
    Node* child[1 << LOG] = {};

    Node() {}

    Node(const T& data) : data(data) {}
  };

  Node* root;

  PersistentArray() : root(nullptr) {}

  T get(Node* t, int k) {
    if (k == 0) return t->data;
    return get(t->child[k & ((1 << LOG) - 1)], k >> LOG);
  }

  T get(const int& k) { return get(root, k); }

  std::pair<Node*, T*> mutable_get(Node* t, int k) {
    t = t ? new Node(*t) : new Node();
    if (k == 0) return {t, &t->data};
    auto p = mutable_get(t->child[k & ((1 << LOG) - 1)], k >> LOG);
    t->child[k & ((1 << LOG) - 1)] = 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& data, int k) {
    if (!t) t = new Node();
    if (k == 0) {
      t->data = data;
      return t;
    }
    auto p = build(t->child[k & ((1 << LOG) - 1)], data, k >> LOG);
    t->child[k & ((1 << LOG) - 1)] = p;
    return t;
  }

  void build(const std::vector<T>& v) {
    root = nullptr;
    for (int i = 0; i < (int)v.size(); i++) {
      root = build(root, v[i], i);
    }
  }
};
#line 4 "test/unittest/persistent-array.test.cpp"

#include <cassert>
#line 7 "test/unittest/persistent-array.test.cpp"

int main() {
  PersistentArray<int, 2> original;
  original.build(std::vector<int>{10, 20, 30, 40, 50});
  assert(original.get(0) == 10);
  assert(original.get(4) == 50);

  auto first = original;
  *first.mutable_get(1) = 200;
  *first.mutable_get(4) = 500;
  assert(original.get(1) == 20);
  assert(original.get(4) == 50);
  assert(first.get(1) == 200);
  assert(first.get(4) == 500);

  auto second = first;
  *second.mutable_get(0) = -1;
  assert(first.get(0) == 10);
  assert(second.get(0) == -1);
}

Back to top page