Persistent Dynamic Array
(ds/dynamic_array/persistent_dynamic_array.hpp)

View this file on GitHub
Last update: 2026-08-12 03:11:00+09:00
Include: #include "ds/dynamic_array/persistent_dynamic_array.hpp"

Overview

PersistentDynamicArray is a path-copying implicit treap. It acts like a persistent version of DynamicArray: update operations return a new array and leave the old version available.

Nodes are stored in a shared stable-slot pool and refer to children by integer index. Intrusive reference counts reclaim a node once no version or parent node depends on it, and reclaimed slots are reused by later updates. References returned by at, front, and back remain valid only while a live version depends on their node.

The structure supports index-based insertion, deletion, point assignment, reversal, rotation, splitting, and concatenation. Untouched subtrees are shared between versions.

set returns a new persistent version. set_inplace mutates this handle with copy-on-write: it clones shared nodes on the search path and reuses unique ones, while every other live version remains unchanged. Structural treap operations continue to use the persistent-returning interface.

Complexity Notation

N is the current number of elements in the array.
M is the number of inserted or appended elements.
K is the number of elements returned by to_vector.

Template Parameters

T: The underlying data type of the elements.

Constructors

PersistentDynamicArray() Constructs an empty array. ($O(1)$)
PersistentDynamicArray(int n) Constructs an array with n value-initialized elements. ($O(N)$)
PersistentDynamicArray(int n, const T& value) Constructs an array with n copies of value. ($O(N)$)
PersistentDynamicArray(const std::vector<T>& v) Constructs an array initialized with elements from v. ($O(N)$)
PersistentDynamicArray(std::vector<T>&& v) Constructs an array by moving elements from v. ($O(N)$)
PersistentDynamicArray(std::initializer_list<T> init) Constructs an array initialized with an initializer list. ($O(N)$)

Methods

Method	Description	Complexity
`int size() const`	Returns the number of elements.	$O(1)$
`bool empty() const`	Returns whether the array is empty.	$O(1)$
`void release()`	Releases this version immediately and makes this handle empty.	$O(F)$
`std::size_t node_count() const`	Returns live nodes in the shared version family.	$O(1)$
`PersistentDynamicArray clear() const`	Returns an empty version.	$O(1)$
`PersistentDynamicArray insert(int pos, T val) const`	Returns a version with `val` inserted before index `pos`.	Expected $O(\log N)$
`PersistentDynamicArray insert(int pos, const std::vector<T>& v) const`	Returns a version with all elements of `v` inserted before index `pos`.	Expected $O(M + \log N)$
`PersistentDynamicArray insert(int pos, const PersistentDynamicArray& other) const`	Returns a version with `other` inserted before index `pos`. Versions sharing a pool reuse its nodes; an independently constructed array is copied into this pool.	Expected $O(\log N)$ with a shared pool; $O(M + \log N)$ otherwise
`PersistentDynamicArray push_back(T val) const`, `push_front(T val) const`	Returns a version with one element added.	Expected $O(\log N)$
`PersistentDynamicArray append(...) const`	Appends a vector or another persistent dynamic array.	Expected $O(M + \log N)$ for a vector or independent array; $O(\log N)$ for a version sharing the pool
`PersistentDynamicArray erase(int pos) const`	Returns a version with the element at `pos` removed.	Expected $O(\log N)$
`PersistentDynamicArray erase(int l, int r) const`	Returns a version with `[l, r)` removed.	Expected $O(\log N)$
`PersistentDynamicArray pop_back() const`, `pop_front() const`	Returns a version with one element removed.	Expected $O(\log N)$
`const T& at(int pos) const`, `operator[]`	Returns the element at `pos`.	Expected $O(\log N)$
`T get(int pos) const`	Returns a copy of the element at `pos`.	Expected $O(\log N)$
`const T& front() const`, `back() const`	Returns the first or last element.	Expected $O(\log N)$
`PersistentDynamicArray set(int pos, T val) const`	Returns a version where index `pos` is overwritten by `val`.	Expected $O(\log N)$
`void set_inplace(int pos, T val)`	Overwrites index `pos` in this version using copy-on-write.	Expected $O(\log N)$
`PersistentDynamicArray reverse(int l, int r) const`	Returns a version with `[l, r)` reversed.	Expected $O(\log N)$
`PersistentDynamicArray reverse() const`	Returns a version with the whole array reversed.	$O(1)$
`PersistentDynamicArray rotate(int l, int m, int r) const`	Returns a version where `[m, r)` is moved before `[l, m)`, like `std::rotate`.	Expected $O(\log N)$
`std::pair<PersistentDynamicArray, PersistentDynamicArray> split(int pos) const`	Returns `{prefix, suffix}` split at `pos`.	Expected $O(\log N)$
`PersistentDynamicArray split_off(int pos) const`	Returns the suffix `[pos, N)` while leaving the current version unchanged.	Expected $O(\log N)$
`std::vector<T> to_vector() const`	Dumps the entire array.	$O(N)$
`std::vector<T> to_vector(int l, int r) const`	Dumps `[l, r)`, where `K = r - l`.	$O(K + \log N)$

Here $F$ is the number of nodes that become unreachable. Destruction and assignment release roots automatically.

Example

#include "ds/dynamic_array/persistent_dynamic_array.hpp"

#include <iostream>

using namespace m1une::ds;

int main() {
    PersistentDynamicArray<int> a = {1, 2, 3, 4, 5};
    auto b = a.insert(2, 10);      // {1, 2, 10, 3, 4, 5}
    auto c = b.reverse(1, 5);      // {1, 4, 3, 10, 2, 5}
    auto d = c.erase(2).set(0, 7); // {7, 4, 10, 2, 5}

    for (int x : a.to_vector()) std::cout << x << " ";
    std::cout << "\n";
    for (int x : d.to_vector()) std::cout << x << " ";
    std::cout << "\n";
}

Depends on

ds/detail/persistent_binary_node_pool.hpp

Verified with

Code

#ifndef M1UNE_PERSISTENT_DYNAMIC_ARRAY_HPP
#define M1UNE_PERSISTENT_DYNAMIC_ARRAY_HPP 1

#include <cassert>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <deque>
#include <initializer_list>
#include <memory>
#include <utility>
#include <vector>

#include "../detail/persistent_binary_node_pool.hpp"

namespace m1une {
namespace ds {

template <typename T>
struct PersistentDynamicArray {
   private:
    struct Node {
        T val;
        int priority;
        int count;
        int l, r;
        bool rev;

        Node(T value, int node_priority, int node_count, int left, int right, bool reversed)
            : val(std::move(value)),
              priority(node_priority),
              count(node_count),
              l(left),
              r(right),
              rev(reversed) {}
    };

    struct BuildNode {
        T val;
        int priority;
        int l, r;

        BuildNode(T value, int node_priority) : val(std::move(value)), priority(node_priority), l(-1), r(-1) {}
    };

    int root;
    std::uint32_t rng_state;
    using Pool = detail::PersistentBinaryNodePool<Node>;

    std::shared_ptr<Pool> pool;

    int subtree_size(int t) const {
        return t == -1 ? 0 : (*pool)[t].count;
    }

    static std::uint32_t next_state(std::uint32_t state) {
        state ^= state << 13;
        state ^= state >> 17;
        state ^= state << 5;
        return state == 0 ? 1 : state;
    }

    static int next_priority(std::uint32_t& state) {
        state = next_state(state);
        return int(state);
    }

    int make_node(T val, int priority, bool rev, int l, int r) const {
        int count = 1 + subtree_size(l) + subtree_size(r);
        return pool->emplace(std::move(val), priority, count, l, r, rev);
    }

    int reversed_node(int t) const {
        if (t == -1) return -1;
        const Node& node = (*pool)[t];
        return make_node(node.val, node.priority, !node.rev, node.l, node.r);
    }

    int push(int t) const {
        if (t == -1 || !(*pool)[t].rev) return t;
        Node node = (*pool)[t];
        int l = reversed_node(node.r);
        int r = reversed_node(node.l);
        return make_node(std::move(node.val), node.priority, false, l, r);
    }

    int merge(int l, int r) const {
        if (l == -1 || r == -1) return l == -1 ? r : l;
        if ((*pool)[l].priority > (*pool)[r].priority) {
            Node node = (*pool)[push(l)];
            int right = merge(node.r, r);
            return make_node(std::move(node.val), node.priority, false, node.l, right);
        }
        Node node = (*pool)[push(r)];
        int left = merge(l, node.l);
        return make_node(std::move(node.val), node.priority, false, left, node.r);
    }

    std::pair<int, int> split_node(int t, int pos) const {
        if (t == -1) return {-1, -1};
        Node node = (*pool)[push(t)];
        int left_count = subtree_size(node.l);
        if (pos <= left_count) {
            auto [a, b] = split_node(node.l, pos);
            return {a, make_node(std::move(node.val), node.priority, false, b, node.r)};
        }
        auto [a, b] = split_node(node.r, pos - left_count - 1);
        return {make_node(std::move(node.val), node.priority, false, node.l, a), b};
    }

    int set_node(int t, int pos, T val) const {
        Node node = (*pool)[push(t)];
        int left_count = subtree_size(node.l);
        if (pos < left_count) {
            int l = set_node(node.l, pos, std::move(val));
            return make_node(std::move(node.val), node.priority, false, l, node.r);
        }
        if (pos == left_count) {
            return make_node(std::move(val), node.priority, false, node.l, node.r);
        }
        int r = set_node(node.r, pos - left_count - 1, std::move(val));
        return make_node(std::move(node.val), node.priority, false, node.l, r);
    }

    int set_node_inplace(int t, int pos, T val, bool inherited_reversed = false) const {
        t = pool->clone_if_shared(t);
        const bool reversed = inherited_reversed ^ (*pool)[t].rev;
        const int logical_left = reversed ? (*pool)[t].r : (*pool)[t].l;
        const int left_count = subtree_size(logical_left);
        if (pos < left_count) {
            int child = set_node_inplace(logical_left, pos, std::move(val), reversed);
            if (reversed) {
                pool->replace((*pool)[t].r, child);
            } else {
                pool->replace((*pool)[t].l, child);
            }
        } else if (pos == left_count) {
            (*pool)[t].val = std::move(val);
        } else {
            const int logical_right = reversed ? (*pool)[t].l : (*pool)[t].r;
            int child = set_node_inplace(logical_right, pos - left_count - 1, std::move(val), reversed);
            if (reversed) {
                pool->replace((*pool)[t].l, child);
            } else {
                pool->replace((*pool)[t].r, child);
            }
        }
        return t;
    }

    int find_node(int t, int pos) const {
        bool reversed = false;
        while (t != -1) {
            const Node& node = (*pool)[t];
            bool cur_reversed = reversed ^ node.rev;
            int l = cur_reversed ? node.r : node.l;
            int r = cur_reversed ? node.l : node.r;
            int left_count = subtree_size(l);
            if (pos < left_count) {
                t = l;
                reversed = cur_reversed;
            } else if (pos == left_count) {
                return t;
            } else {
                pos -= left_count + 1;
                t = r;
                reversed = cur_reversed;
            }
        }
        return -1;
    }

    void dump_dfs(int t, std::vector<T>& res, bool reversed = false) const {
        if (t == -1) return;
        const Node& node = (*pool)[t];
        bool cur_reversed = reversed ^ node.rev;
        int l = cur_reversed ? node.r : node.l;
        int r = cur_reversed ? node.l : node.r;
        dump_dfs(l, res, cur_reversed);
        res.push_back(node.val);
        dump_dfs(r, res, cur_reversed);
    }

    void dump_range_dfs(int t, int ql, int qr, int offset, std::vector<T>& res, bool reversed = false) const {
        if (t == -1 || qr <= offset || offset + (*pool)[t].count <= ql) return;
        const Node& node = (*pool)[t];
        bool cur_reversed = reversed ^ node.rev;
        int l = cur_reversed ? node.r : node.l;
        int r = cur_reversed ? node.l : node.r;
        int left_count = subtree_size(l);
        int node_pos = offset + left_count;
        dump_range_dfs(l, ql, qr, offset, res, cur_reversed);
        if (ql <= node_pos && node_pos < qr) res.push_back(node.val);
        dump_range_dfs(r, ql, qr, node_pos + 1, res, cur_reversed);
    }

    int build_from_nodes(std::vector<BuildNode>& nodes, int t) const {
        if (t == -1) return -1;
        int l = build_from_nodes(nodes, nodes[t].l);
        int r = build_from_nodes(nodes, nodes[t].r);
        return make_node(std::move(nodes[t].val), nodes[t].priority, false, l, r);
    }

    int build_cartesian(std::vector<BuildNode>& nodes) const {
        if (nodes.empty()) return -1;
        std::vector<int> stack;
        stack.reserve(nodes.size());
        for (int i = 0; i < int(nodes.size()); i++) {
            int left_child = -1;
            while (!stack.empty() && nodes[stack.back()].priority < nodes[i].priority) {
                left_child = stack.back();
                stack.pop_back();
            }
            nodes[i].l = left_child;
            if (!stack.empty()) nodes[stack.back()].r = i;
            stack.push_back(i);
        }
        return build_from_nodes(nodes, stack.front());
    }

    int build_from_vector(const std::vector<T>& v, std::uint32_t& state) const {
        std::vector<BuildNode> nodes;
        nodes.reserve(v.size());
        for (const T& x : v) nodes.emplace_back(x, next_priority(state));
        return build_cartesian(nodes);
    }

    int build_from_vector(std::vector<T>&& v, std::uint32_t& state) const {
        std::vector<BuildNode> nodes;
        nodes.reserve(v.size());
        for (T& x : v) nodes.emplace_back(std::move(x), next_priority(state));
        return build_cartesian(nodes);
    }

    int import_node(const PersistentDynamicArray& other, int t) const {
        if (t == -1) return -1;
        if (pool == other.pool) return t;
        const Node& node = (*other.pool)[t];
        int l = import_node(other, node.l);
        int r = import_node(other, node.r);
        return make_node(node.val, node.priority, node.rev, l, r);
    }

    explicit PersistentDynamicArray(int node, std::uint32_t state, std::shared_ptr<Pool> node_pool)
        : root(node), rng_state(state), pool(std::move(node_pool)) {
        pool->retain(root);
    }

    PersistentDynamicArray make_version(int node, std::uint32_t state) const {
        PersistentDynamicArray result(node, state, pool);
        pool->discard_unreferenced();
        return result;
    }

   public:
    PersistentDynamicArray()
        : root(-1),
          rng_state(std::uint32_t(std::chrono::steady_clock::now().time_since_epoch().count())),
          pool(std::make_shared<Pool>()) {
        if (rng_state == 0) rng_state = 1;
    }

    explicit PersistentDynamicArray(int n) : PersistentDynamicArray(n, T()) {}

    PersistentDynamicArray(int n, const T& value) : PersistentDynamicArray() {
        assert(0 <= n);
        std::vector<T> v(n, value);
        root = build_from_vector(std::move(v), rng_state);
        pool->retain(root);
        pool->discard_unreferenced();
    }

    explicit PersistentDynamicArray(const std::vector<T>& v) : PersistentDynamicArray() {
        root = build_from_vector(v, rng_state);
        pool->retain(root);
        pool->discard_unreferenced();
    }

    explicit PersistentDynamicArray(std::vector<T>&& v) : PersistentDynamicArray() {
        root = build_from_vector(std::move(v), rng_state);
        pool->retain(root);
        pool->discard_unreferenced();
    }

    PersistentDynamicArray(std::initializer_list<T> init) : PersistentDynamicArray(std::vector<T>(init)) {}

    PersistentDynamicArray(const PersistentDynamicArray& other)
        : root(other.root), rng_state(other.rng_state), pool(other.pool) {
        if (pool) pool->retain(root);
    }

    PersistentDynamicArray(PersistentDynamicArray&& other) noexcept
        : root(other.root), rng_state(other.rng_state), pool(std::move(other.pool)) {
        other.root = -1;
    }

    PersistentDynamicArray& operator=(const PersistentDynamicArray& other) {
        if (this == &other) return *this;
        if (other.pool) other.pool->retain(other.root);
        if (pool) pool->release(root);
        root = other.root;
        rng_state = other.rng_state;
        pool = other.pool;
        return *this;
    }

    PersistentDynamicArray& operator=(PersistentDynamicArray&& other) noexcept {
        if (this == &other) return *this;
        if (pool) pool->release(root);
        root = other.root;
        rng_state = other.rng_state;
        pool = std::move(other.pool);
        other.root = -1;
        return *this;
    }

    ~PersistentDynamicArray() {
        if (pool) pool->release(root);
    }

    int size() const {
        return subtree_size(root);
    }

    bool empty() const {
        return size() == 0;
    }

    void release() {
        if (pool) pool->release(root);
        root = -1;
        pool = std::make_shared<Pool>();
    }

    std::size_t node_count() const { return pool ? pool->size() : 0; }

    PersistentDynamicArray clear() const {
        return make_version(-1, rng_state);
    }

    PersistentDynamicArray insert(int pos, T val) const {
        assert(0 <= pos && pos <= size());
        std::uint32_t next = next_state(rng_state);
        int node = make_node(std::move(val), int(next), false, -1, -1);
        auto [l, r] = split_node(root, pos);
        return make_version(merge(merge(l, node), r), next);
    }

    PersistentDynamicArray insert(int pos, const std::vector<T>& v) const {
        assert(0 <= pos && pos <= size());
        if (v.empty()) return *this;
        std::uint32_t next = rng_state;
        int mid = build_from_vector(v, next);
        auto [l, r] = split_node(root, pos);
        return make_version(merge(merge(l, mid), r), next);
    }

    PersistentDynamicArray insert(int pos, std::vector<T>&& v) const {
        assert(0 <= pos && pos <= size());
        if (v.empty()) return *this;
        std::uint32_t next = rng_state;
        int mid = build_from_vector(std::move(v), next);
        auto [l, r] = split_node(root, pos);
        return make_version(merge(merge(l, mid), r), next);
    }

    PersistentDynamicArray insert(int pos, std::initializer_list<T> init) const {
        return insert(pos, std::vector<T>(init));
    }

    PersistentDynamicArray insert(int pos, const PersistentDynamicArray& other) const {
        assert(0 <= pos && pos <= size());
        if (other.empty()) return *this;
        int mid = import_node(other, other.root);
        auto [l, r] = split_node(root, pos);
        return make_version(merge(merge(l, mid), r), rng_state);
    }

    PersistentDynamicArray push_back(T val) const {
        return insert(size(), std::move(val));
    }

    PersistentDynamicArray push_front(T val) const {
        return insert(0, std::move(val));
    }

    PersistentDynamicArray append(const std::vector<T>& v) const {
        return insert(size(), v);
    }

    PersistentDynamicArray append(std::vector<T>&& v) const {
        return insert(size(), std::move(v));
    }

    PersistentDynamicArray append(const PersistentDynamicArray& other) const {
        return insert(size(), other);
    }

    PersistentDynamicArray erase(int pos) const {
        assert(0 <= pos && pos < size());
        auto [a, b] = split_node(root, pos);
        auto [mid, c] = split_node(b, 1);
        (void)mid;
        return make_version(merge(a, c), rng_state);
    }

    PersistentDynamicArray erase(int l, int r) const {
        assert(0 <= l && l <= r && r <= size());
        if (l == r) return *this;
        auto [a, b] = split_node(root, l);
        auto [mid, c] = split_node(b, r - l);
        (void)mid;
        return make_version(merge(a, c), rng_state);
    }

    PersistentDynamicArray pop_back() const {
        assert(!empty());
        return erase(size() - 1);
    }

    PersistentDynamicArray pop_front() const {
        assert(!empty());
        return erase(0);
    }

    const T& at(int pos) const {
        assert(0 <= pos && pos < size());
        return (*pool)[find_node(root, pos)].val;
    }

    const T& operator[](int pos) const {
        return at(pos);
    }

    const T& front() const {
        assert(!empty());
        return at(0);
    }

    const T& back() const {
        assert(!empty());
        return at(size() - 1);
    }

    T get(int pos) const {
        return at(pos);
    }

    PersistentDynamicArray set(int pos, T val) const {
        assert(0 <= pos && pos < size());
        return make_version(set_node(root, pos, std::move(val)), rng_state);
    }

    void set_inplace(int pos, T val) {
        assert(0 <= pos && pos < size());
        int next_root = set_node_inplace(root, pos, std::move(val));
        pool->replace(root, next_root);
        pool->discard_unreferenced();
    }

    PersistentDynamicArray reverse(int l, int r) const {
        assert(0 <= l && l <= r && r <= size());
        if (l == r) return *this;
        auto [a, b] = split_node(root, l);
        auto [mid, c] = split_node(b, r - l);
        return make_version(merge(merge(a, reversed_node(mid)), c), rng_state);
    }

    PersistentDynamicArray reverse() const {
        return make_version(reversed_node(root), rng_state);
    }

    PersistentDynamicArray rotate(int l, int m, int r) const {
        assert(0 <= l && l <= m && m <= r && r <= size());
        if (l == m || m == r) return *this;
        auto [a, b] = split_node(root, l);
        auto [c, d] = split_node(b, m - l);
        auto [e, f] = split_node(d, r - m);
        return make_version(merge(merge(a, e), merge(c, f)), rng_state);
    }

    std::pair<PersistentDynamicArray, PersistentDynamicArray> split(int pos) const {
        assert(0 <= pos && pos <= size());
        auto [l, r] = split_node(root, pos);
        PersistentDynamicArray left(l, rng_state, pool);
        PersistentDynamicArray right(r, rng_state, pool);
        pool->discard_unreferenced();
        return {std::move(left), std::move(right)};
    }

    PersistentDynamicArray split_off(int pos) const {
        assert(0 <= pos && pos <= size());
        return make_version(split_node(root, pos).second, rng_state);
    }

    std::vector<T> to_vector() const {
        std::vector<T> res;
        res.reserve(size());
        dump_dfs(root, res);
        return res;
    }

    std::vector<T> to_vector(int l, int r) const {
        assert(0 <= l && l <= r && r <= size());
        std::vector<T> res;
        res.reserve(r - l);
        dump_range_dfs(root, l, r, 0, res);
        return res;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_PERSISTENT_DYNAMIC_ARRAY_HPP

#line 1 "ds/dynamic_array/persistent_dynamic_array.hpp"



#include <cassert>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <deque>
#include <initializer_list>
#include <memory>
#include <utility>
#include <vector>

#line 1 "ds/detail/persistent_binary_node_pool.hpp"



#line 7 "ds/detail/persistent_binary_node_pool.hpp"
#include <limits>
#include <optional>
#line 11 "ds/detail/persistent_binary_node_pool.hpp"

namespace m1une {
namespace ds {
namespace detail {

// Node must have integer `l` and `r` members. New nodes initially have no
// owner; discard_unreferenced() removes temporary path-copy nodes after the
// result roots have been retained.
template <class Node, int null_node = -1>
struct PersistentBinaryNodePool {
   private:
    std::deque<std::optional<Node>> _nodes;
    std::vector<int> _references;
    std::vector<int> _next_free;
    std::vector<int> _unowned;
    int _first_free = -1;
    std::size_t _live_nodes = 0;

    void release_zero(int node) {
        assert(node != null_node && _nodes[node].has_value());
        int left = (*_nodes[node]).l;
        int right = (*_nodes[node]).r;
        _nodes[node].reset();
        _next_free[node] = _first_free;
        _first_free = node;
        --_live_nodes;
        if (left != null_node && --_references[left] == 0) release_zero(left);
        if (right != null_node && --_references[right] == 0) release_zero(right);
    }

   public:
    PersistentBinaryNodePool() {
        if constexpr (null_node == 0) {
            _nodes.emplace_back();
            _references.push_back(0);
            _next_free.push_back(-1);
        }
    }

    Node& operator[](int node) {
        assert(node != null_node && _nodes[node].has_value());
        return *_nodes[node];
    }

    const Node& operator[](int node) const {
        assert(node != null_node && _nodes[node].has_value());
        return *_nodes[node];
    }

    template <class... Args>
    int emplace(Args&&... args) {
        int result;
        if (_first_free == -1) {
            assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
            result = int(_nodes.size());
            _nodes.emplace_back(std::in_place, std::forward<Args>(args)...);
            _references.push_back(0);
            _next_free.push_back(-1);
        } else {
            result = _first_free;
            _first_free = _next_free[result];
            _nodes[result].emplace(std::forward<Args>(args)...);
            _references[result] = 0;
        }
        retain((*_nodes[result]).l);
        retain((*_nodes[result]).r);
        _unowned.push_back(result);
        ++_live_nodes;
        return result;
    }

    void retain(int node) {
        if (node != null_node) {
            assert(_nodes[node].has_value());
            ++_references[node];
        }
    }

    void release(int node) {
        if (node == null_node) return;
        assert(_nodes[node].has_value() && _references[node] > 0);
        if (--_references[node] == 0) release_zero(node);
    }

    bool unique(int node) const {
        return node == null_node || _references[node] == 1;
    }

    int clone(int node) {
        assert(node != null_node && _nodes[node].has_value());
        return emplace(*_nodes[node]);
    }

    // Returns node itself when it has one owner, otherwise an unowned clone.
    // A returned clone becomes owned when a root or parent edge retains it.
    int clone_if_shared(int node) {
        if (unique(node)) return node;
        return clone(node);
    }

    void replace(int& edge, int node) {
        if (edge == node) return;
        retain(node);
        int old = edge;
        edge = node;
        release(old);
    }

    void discard_unreferenced() {
        while (!_unowned.empty()) {
            int node = _unowned.back();
            _unowned.pop_back();
            if (_nodes[node].has_value() && _references[node] == 0) release_zero(node);
        }
    }

    void reserve(std::size_t) {}

    int next_index() const { return _first_free == -1 ? int(_nodes.size()) : _first_free; }

    std::size_t size() const { return _live_nodes; }
};

}  // namespace detail
}  // namespace ds
}  // namespace m1une


#line 15 "ds/dynamic_array/persistent_dynamic_array.hpp"

namespace m1une {
namespace ds {

template <typename T>
struct PersistentDynamicArray {
   private:
    struct Node {
        T val;
        int priority;
        int count;
        int l, r;
        bool rev;

        Node(T value, int node_priority, int node_count, int left, int right, bool reversed)
            : val(std::move(value)),
              priority(node_priority),
              count(node_count),
              l(left),
              r(right),
              rev(reversed) {}
    };

    struct BuildNode {
        T val;
        int priority;
        int l, r;

        BuildNode(T value, int node_priority) : val(std::move(value)), priority(node_priority), l(-1), r(-1) {}
    };

    int root;
    std::uint32_t rng_state;
    using Pool = detail::PersistentBinaryNodePool<Node>;

    std::shared_ptr<Pool> pool;

    int subtree_size(int t) const {
        return t == -1 ? 0 : (*pool)[t].count;
    }

    static std::uint32_t next_state(std::uint32_t state) {
        state ^= state << 13;
        state ^= state >> 17;
        state ^= state << 5;
        return state == 0 ? 1 : state;
    }

    static int next_priority(std::uint32_t& state) {
        state = next_state(state);
        return int(state);
    }

    int make_node(T val, int priority, bool rev, int l, int r) const {
        int count = 1 + subtree_size(l) + subtree_size(r);
        return pool->emplace(std::move(val), priority, count, l, r, rev);
    }

    int reversed_node(int t) const {
        if (t == -1) return -1;
        const Node& node = (*pool)[t];
        return make_node(node.val, node.priority, !node.rev, node.l, node.r);
    }

    int push(int t) const {
        if (t == -1 || !(*pool)[t].rev) return t;
        Node node = (*pool)[t];
        int l = reversed_node(node.r);
        int r = reversed_node(node.l);
        return make_node(std::move(node.val), node.priority, false, l, r);
    }

    int merge(int l, int r) const {
        if (l == -1 || r == -1) return l == -1 ? r : l;
        if ((*pool)[l].priority > (*pool)[r].priority) {
            Node node = (*pool)[push(l)];
            int right = merge(node.r, r);
            return make_node(std::move(node.val), node.priority, false, node.l, right);
        }
        Node node = (*pool)[push(r)];
        int left = merge(l, node.l);
        return make_node(std::move(node.val), node.priority, false, left, node.r);
    }

    std::pair<int, int> split_node(int t, int pos) const {
        if (t == -1) return {-1, -1};
        Node node = (*pool)[push(t)];
        int left_count = subtree_size(node.l);
        if (pos <= left_count) {
            auto [a, b] = split_node(node.l, pos);
            return {a, make_node(std::move(node.val), node.priority, false, b, node.r)};
        }
        auto [a, b] = split_node(node.r, pos - left_count - 1);
        return {make_node(std::move(node.val), node.priority, false, node.l, a), b};
    }

    int set_node(int t, int pos, T val) const {
        Node node = (*pool)[push(t)];
        int left_count = subtree_size(node.l);
        if (pos < left_count) {
            int l = set_node(node.l, pos, std::move(val));
            return make_node(std::move(node.val), node.priority, false, l, node.r);
        }
        if (pos == left_count) {
            return make_node(std::move(val), node.priority, false, node.l, node.r);
        }
        int r = set_node(node.r, pos - left_count - 1, std::move(val));
        return make_node(std::move(node.val), node.priority, false, node.l, r);
    }

    int set_node_inplace(int t, int pos, T val, bool inherited_reversed = false) const {
        t = pool->clone_if_shared(t);
        const bool reversed = inherited_reversed ^ (*pool)[t].rev;
        const int logical_left = reversed ? (*pool)[t].r : (*pool)[t].l;
        const int left_count = subtree_size(logical_left);
        if (pos < left_count) {
            int child = set_node_inplace(logical_left, pos, std::move(val), reversed);
            if (reversed) {
                pool->replace((*pool)[t].r, child);
            } else {
                pool->replace((*pool)[t].l, child);
            }
        } else if (pos == left_count) {
            (*pool)[t].val = std::move(val);
        } else {
            const int logical_right = reversed ? (*pool)[t].l : (*pool)[t].r;
            int child = set_node_inplace(logical_right, pos - left_count - 1, std::move(val), reversed);
            if (reversed) {
                pool->replace((*pool)[t].l, child);
            } else {
                pool->replace((*pool)[t].r, child);
            }
        }
        return t;
    }

    int find_node(int t, int pos) const {
        bool reversed = false;
        while (t != -1) {
            const Node& node = (*pool)[t];
            bool cur_reversed = reversed ^ node.rev;
            int l = cur_reversed ? node.r : node.l;
            int r = cur_reversed ? node.l : node.r;
            int left_count = subtree_size(l);
            if (pos < left_count) {
                t = l;
                reversed = cur_reversed;
            } else if (pos == left_count) {
                return t;
            } else {
                pos -= left_count + 1;
                t = r;
                reversed = cur_reversed;
            }
        }
        return -1;
    }

    void dump_dfs(int t, std::vector<T>& res, bool reversed = false) const {
        if (t == -1) return;
        const Node& node = (*pool)[t];
        bool cur_reversed = reversed ^ node.rev;
        int l = cur_reversed ? node.r : node.l;
        int r = cur_reversed ? node.l : node.r;
        dump_dfs(l, res, cur_reversed);
        res.push_back(node.val);
        dump_dfs(r, res, cur_reversed);
    }

    void dump_range_dfs(int t, int ql, int qr, int offset, std::vector<T>& res, bool reversed = false) const {
        if (t == -1 || qr <= offset || offset + (*pool)[t].count <= ql) return;
        const Node& node = (*pool)[t];
        bool cur_reversed = reversed ^ node.rev;
        int l = cur_reversed ? node.r : node.l;
        int r = cur_reversed ? node.l : node.r;
        int left_count = subtree_size(l);
        int node_pos = offset + left_count;
        dump_range_dfs(l, ql, qr, offset, res, cur_reversed);
        if (ql <= node_pos && node_pos < qr) res.push_back(node.val);
        dump_range_dfs(r, ql, qr, node_pos + 1, res, cur_reversed);
    }

    int build_from_nodes(std::vector<BuildNode>& nodes, int t) const {
        if (t == -1) return -1;
        int l = build_from_nodes(nodes, nodes[t].l);
        int r = build_from_nodes(nodes, nodes[t].r);
        return make_node(std::move(nodes[t].val), nodes[t].priority, false, l, r);
    }

    int build_cartesian(std::vector<BuildNode>& nodes) const {
        if (nodes.empty()) return -1;
        std::vector<int> stack;
        stack.reserve(nodes.size());
        for (int i = 0; i < int(nodes.size()); i++) {
            int left_child = -1;
            while (!stack.empty() && nodes[stack.back()].priority < nodes[i].priority) {
                left_child = stack.back();
                stack.pop_back();
            }
            nodes[i].l = left_child;
            if (!stack.empty()) nodes[stack.back()].r = i;
            stack.push_back(i);
        }
        return build_from_nodes(nodes, stack.front());
    }

    int build_from_vector(const std::vector<T>& v, std::uint32_t& state) const {
        std::vector<BuildNode> nodes;
        nodes.reserve(v.size());
        for (const T& x : v) nodes.emplace_back(x, next_priority(state));
        return build_cartesian(nodes);
    }

    int build_from_vector(std::vector<T>&& v, std::uint32_t& state) const {
        std::vector<BuildNode> nodes;
        nodes.reserve(v.size());
        for (T& x : v) nodes.emplace_back(std::move(x), next_priority(state));
        return build_cartesian(nodes);
    }

    int import_node(const PersistentDynamicArray& other, int t) const {
        if (t == -1) return -1;
        if (pool == other.pool) return t;
        const Node& node = (*other.pool)[t];
        int l = import_node(other, node.l);
        int r = import_node(other, node.r);
        return make_node(node.val, node.priority, node.rev, l, r);
    }

    explicit PersistentDynamicArray(int node, std::uint32_t state, std::shared_ptr<Pool> node_pool)
        : root(node), rng_state(state), pool(std::move(node_pool)) {
        pool->retain(root);
    }

    PersistentDynamicArray make_version(int node, std::uint32_t state) const {
        PersistentDynamicArray result(node, state, pool);
        pool->discard_unreferenced();
        return result;
    }

   public:
    PersistentDynamicArray()
        : root(-1),
          rng_state(std::uint32_t(std::chrono::steady_clock::now().time_since_epoch().count())),
          pool(std::make_shared<Pool>()) {
        if (rng_state == 0) rng_state = 1;
    }

    explicit PersistentDynamicArray(int n) : PersistentDynamicArray(n, T()) {}

    PersistentDynamicArray(int n, const T& value) : PersistentDynamicArray() {
        assert(0 <= n);
        std::vector<T> v(n, value);
        root = build_from_vector(std::move(v), rng_state);
        pool->retain(root);
        pool->discard_unreferenced();
    }

    explicit PersistentDynamicArray(const std::vector<T>& v) : PersistentDynamicArray() {
        root = build_from_vector(v, rng_state);
        pool->retain(root);
        pool->discard_unreferenced();
    }

    explicit PersistentDynamicArray(std::vector<T>&& v) : PersistentDynamicArray() {
        root = build_from_vector(std::move(v), rng_state);
        pool->retain(root);
        pool->discard_unreferenced();
    }

    PersistentDynamicArray(std::initializer_list<T> init) : PersistentDynamicArray(std::vector<T>(init)) {}

    PersistentDynamicArray(const PersistentDynamicArray& other)
        : root(other.root), rng_state(other.rng_state), pool(other.pool) {
        if (pool) pool->retain(root);
    }

    PersistentDynamicArray(PersistentDynamicArray&& other) noexcept
        : root(other.root), rng_state(other.rng_state), pool(std::move(other.pool)) {
        other.root = -1;
    }

    PersistentDynamicArray& operator=(const PersistentDynamicArray& other) {
        if (this == &other) return *this;
        if (other.pool) other.pool->retain(other.root);
        if (pool) pool->release(root);
        root = other.root;
        rng_state = other.rng_state;
        pool = other.pool;
        return *this;
    }

    PersistentDynamicArray& operator=(PersistentDynamicArray&& other) noexcept {
        if (this == &other) return *this;
        if (pool) pool->release(root);
        root = other.root;
        rng_state = other.rng_state;
        pool = std::move(other.pool);
        other.root = -1;
        return *this;
    }

    ~PersistentDynamicArray() {
        if (pool) pool->release(root);
    }

    int size() const {
        return subtree_size(root);
    }

    bool empty() const {
        return size() == 0;
    }

    void release() {
        if (pool) pool->release(root);
        root = -1;
        pool = std::make_shared<Pool>();
    }

    std::size_t node_count() const { return pool ? pool->size() : 0; }

    PersistentDynamicArray clear() const {
        return make_version(-1, rng_state);
    }

    PersistentDynamicArray insert(int pos, T val) const {
        assert(0 <= pos && pos <= size());
        std::uint32_t next = next_state(rng_state);
        int node = make_node(std::move(val), int(next), false, -1, -1);
        auto [l, r] = split_node(root, pos);
        return make_version(merge(merge(l, node), r), next);
    }

    PersistentDynamicArray insert(int pos, const std::vector<T>& v) const {
        assert(0 <= pos && pos <= size());
        if (v.empty()) return *this;
        std::uint32_t next = rng_state;
        int mid = build_from_vector(v, next);
        auto [l, r] = split_node(root, pos);
        return make_version(merge(merge(l, mid), r), next);
    }

    PersistentDynamicArray insert(int pos, std::vector<T>&& v) const {
        assert(0 <= pos && pos <= size());
        if (v.empty()) return *this;
        std::uint32_t next = rng_state;
        int mid = build_from_vector(std::move(v), next);
        auto [l, r] = split_node(root, pos);
        return make_version(merge(merge(l, mid), r), next);
    }

    PersistentDynamicArray insert(int pos, std::initializer_list<T> init) const {
        return insert(pos, std::vector<T>(init));
    }

    PersistentDynamicArray insert(int pos, const PersistentDynamicArray& other) const {
        assert(0 <= pos && pos <= size());
        if (other.empty()) return *this;
        int mid = import_node(other, other.root);
        auto [l, r] = split_node(root, pos);
        return make_version(merge(merge(l, mid), r), rng_state);
    }

    PersistentDynamicArray push_back(T val) const {
        return insert(size(), std::move(val));
    }

    PersistentDynamicArray push_front(T val) const {
        return insert(0, std::move(val));
    }

    PersistentDynamicArray append(const std::vector<T>& v) const {
        return insert(size(), v);
    }

    PersistentDynamicArray append(std::vector<T>&& v) const {
        return insert(size(), std::move(v));
    }

    PersistentDynamicArray append(const PersistentDynamicArray& other) const {
        return insert(size(), other);
    }

    PersistentDynamicArray erase(int pos) const {
        assert(0 <= pos && pos < size());
        auto [a, b] = split_node(root, pos);
        auto [mid, c] = split_node(b, 1);
        (void)mid;
        return make_version(merge(a, c), rng_state);
    }

    PersistentDynamicArray erase(int l, int r) const {
        assert(0 <= l && l <= r && r <= size());
        if (l == r) return *this;
        auto [a, b] = split_node(root, l);
        auto [mid, c] = split_node(b, r - l);
        (void)mid;
        return make_version(merge(a, c), rng_state);
    }

    PersistentDynamicArray pop_back() const {
        assert(!empty());
        return erase(size() - 1);
    }

    PersistentDynamicArray pop_front() const {
        assert(!empty());
        return erase(0);
    }

    const T& at(int pos) const {
        assert(0 <= pos && pos < size());
        return (*pool)[find_node(root, pos)].val;
    }

    const T& operator[](int pos) const {
        return at(pos);
    }

    const T& front() const {
        assert(!empty());
        return at(0);
    }

    const T& back() const {
        assert(!empty());
        return at(size() - 1);
    }

    T get(int pos) const {
        return at(pos);
    }

    PersistentDynamicArray set(int pos, T val) const {
        assert(0 <= pos && pos < size());
        return make_version(set_node(root, pos, std::move(val)), rng_state);
    }

    void set_inplace(int pos, T val) {
        assert(0 <= pos && pos < size());
        int next_root = set_node_inplace(root, pos, std::move(val));
        pool->replace(root, next_root);
        pool->discard_unreferenced();
    }

    PersistentDynamicArray reverse(int l, int r) const {
        assert(0 <= l && l <= r && r <= size());
        if (l == r) return *this;
        auto [a, b] = split_node(root, l);
        auto [mid, c] = split_node(b, r - l);
        return make_version(merge(merge(a, reversed_node(mid)), c), rng_state);
    }

    PersistentDynamicArray reverse() const {
        return make_version(reversed_node(root), rng_state);
    }

    PersistentDynamicArray rotate(int l, int m, int r) const {
        assert(0 <= l && l <= m && m <= r && r <= size());
        if (l == m || m == r) return *this;
        auto [a, b] = split_node(root, l);
        auto [c, d] = split_node(b, m - l);
        auto [e, f] = split_node(d, r - m);
        return make_version(merge(merge(a, e), merge(c, f)), rng_state);
    }

    std::pair<PersistentDynamicArray, PersistentDynamicArray> split(int pos) const {
        assert(0 <= pos && pos <= size());
        auto [l, r] = split_node(root, pos);
        PersistentDynamicArray left(l, rng_state, pool);
        PersistentDynamicArray right(r, rng_state, pool);
        pool->discard_unreferenced();
        return {std::move(left), std::move(right)};
    }

    PersistentDynamicArray split_off(int pos) const {
        assert(0 <= pos && pos <= size());
        return make_version(split_node(root, pos).second, rng_state);
    }

    std::vector<T> to_vector() const {
        std::vector<T> res;
        res.reserve(size());
        dump_dfs(root, res);
        return res;
    }

    std::vector<T> to_vector(int l, int r) const {
        assert(0 <= l && l <= r && r <= size());
        std::vector<T> res;
        res.reserve(r - l);
        dump_range_dfs(root, l, r, 0, res);
        return res;
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Persistent Dynamic Array
(ds/dynamic_array/persistent_dynamic_array.hpp)

Overview

Complexity Notation

Template Parameters

Constructors

Methods

Example

Depends on

Verified with

Code

Persistent Dynamic Array (ds/dynamic_array/persistent_dynamic_array.hpp)

Overview

Complexity Notation

Template Parameters

Constructors

Methods

Example

Depends on

Verified with

Code

Persistent Dynamic Array
(ds/dynamic_array/persistent_dynamic_array.hpp)