Persistent Dynamic Monoid Array
(ds/dynamic_array/persistent_dynamic_monoid_array.hpp)

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

Overview

PersistentDynamicMonoidArray is a path-copying implicit treap for dynamic sequences with range product queries. Updates return a new sequence and leave older versions available.

Nodes live in a shared stable-slot pool and store integer child indices. Intrusive reference counts reclaim nodes after their final dependent version or parent is released, and later updates reuse their slots.

Each node stores both forward and reversed products, so range reversal works for non-commutative monoids.

set_inplace is a copy-on-write point assignment for a mutable working version. It preserves other versions, clones shared search-path nodes, and updates unique nodes directly. Other update methods retain their persistent-returning semantics.

Template Parameters

• Monoid: A monoid satisfying m1une::monoid::IsMonoid.

Methods

Method	Description	Complexity
int size() const, bool empty() const	Returns the sequence size or whether it 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)$
insert, push_back, push_front, append	Return a version with values inserted. Another version sharing the pool reuses its nodes; an independently constructed array is copied into this pool.	Expected $O(\log N)$ for one value or a shared-pool version; $O(M + \log N)$ for a vector or independent array
erase, pop_back, pop_front	Return a version with values removed.	Expected $O(\log N)$
set	Returns a version with one value replaced.	Expected $O(\log N)$
set_inplace(int pos, T value)	Replaces one value in this version using copy-on-write.	Expected $O(\log N)$
reverse, rotate	Return versions with sequence order changed.	Expected $O(\log N)$; whole-sequence reverse() is $O(1)$
prod, all_prod	Return monoid products over a range or the whole sequence.	Expected $O(\log N)$ for prod; $O(1)$ for all_prod
split, split_off	Return persistent split versions.	Expected $O(\log N)$
to_vector	Dumps a range or the whole sequence.	$O(K + \log N)$ for a range; $O(N)$ for all values

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

Notes

Order-aware monoids should store relative order information such as size and ord, not immutable global indices. For example, monoid::ArgMin returns ord relative to the queried range, so it remains valid after insertions, deletions, and reversals.

Example

#include "ds/dynamic_array/persistent_dynamic_monoid_array.hpp"
#include "monoid/add.hpp"
#include <iostream>

using Monoid = m1une::monoid::Add<long long>;
using Array = m1une::ds::PersistentDynamicMonoidArray<Monoid>;

int main() {
    Array a = {1, 2, 3, 4, 5};
    auto b = a.reverse(1, 5);
    auto c = b.set(2, 10);

    // a is still {1, 2, 3, 4, 5}
    // c is {1, 5, 10, 3, 2}
    long long sum = c.prod(0, 4);
    std::cout << sum << "\n";
}

Depends on

• ds/detail/persistent_binary_node_pool.hpp
• Monoid Concept (monoid/concept.hpp)

Verified with

• verify/ds/dynamic_array/persistent_dynamic_monoid_array.test.cpp
• verify/ds/persistent_cow.test.cpp
• verify/ds/persistent_release.test.cpp

Code

#ifndef M1UNE_PERSISTENT_DYNAMIC_MONOID_ARRAY_HPP
#define M1UNE_PERSISTENT_DYNAMIC_MONOID_ARRAY_HPP 1

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

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

namespace m1une {
namespace ds {

template <m1une::monoid::IsMonoid Monoid>
struct PersistentDynamicMonoidArray {
    using T = typename Monoid::value_type;

   private:
    struct Node {
        T val, prod, rprod;
        int priority;
        int count;
        int l, r;
        bool rev;

        Node(T value, T product, T reverse_product, int node_priority, int node_count, int left, int right,
             bool reversed)
            : val(std::move(value)),
              prod(std::move(product)),
              rprod(std::move(reverse_product)),
              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;
    }

    T node_prod(int t) const {
        return t == -1 ? Monoid::id() : (*pool)[t].prod;
    }

    T node_rprod(int t) const {
        return t == -1 ? Monoid::id() : (*pool)[t].rprod;
    }

    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);
    }

    template <typename U>
    static T make_value(const U& value) {
        if constexpr (requires(U x) { Monoid::make(x); }) {
            return Monoid::make(value);
        } else {
            return static_cast<T>(value);
        }
    }

    int make_node(T val, int priority, bool rev, int l, int r) const {
        T prod = Monoid::op(Monoid::op(node_prod(l), val), node_prod(r));
        T rprod = Monoid::op(Monoid::op(node_rprod(r), val), node_rprod(l));
        if (rev) std::swap(prod, rprod);
        int count = 1 + subtree_size(l) + subtree_size(r);
        return pool->emplace(std::move(val), std::move(prod), std::move(rprod), priority, count, l, r, rev);
    }

    int reversed_node(int t) const {
        if (t == -1) return -1;
        Node node = (*pool)[t];
        return make_node(std::move(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);
    }

    void pull(int t) const {
        Node& node = (*pool)[t];
        node.prod = Monoid::op(Monoid::op(node_prod(node.l), node.val), node_prod(node.r));
        node.rprod = Monoid::op(Monoid::op(node_rprod(node.r), node.val), node_rprod(node.l));
        if (node.rev) std::swap(node.prod, node.rprod);
    }

    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);
            }
        }
        pull(t);
        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;
    }

    T prod_dfs(int t, int ql, int qr, int offset, bool reversed = false) const {
        if (t == -1 || qr <= offset || offset + (*pool)[t].count <= ql) return Monoid::id();
        const Node& node = (*pool)[t];
        if (ql <= offset && offset + node.count <= qr) return reversed ? node.rprod : node.prod;
        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;
        T res = prod_dfs(l, ql, qr, offset, cur_reversed);
        if (ql <= node_pos && node_pos < qr) res = Monoid::op(res, node.val);
        return Monoid::op(res, prod_dfs(r, ql, qr, node_pos + 1, cur_reversed));
    }

    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);
    }

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

    int import_node(const PersistentDynamicMonoidArray& 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 PersistentDynamicMonoidArray(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);
    }

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

   public:
    PersistentDynamicMonoidArray()
        : 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 PersistentDynamicMonoidArray(int n) : PersistentDynamicMonoidArray(n, Monoid::id()) {}

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

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

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

    template <typename U>
        requires(!std::same_as<U, T>) && (requires(U x) { Monoid::make(x); } || std::convertible_to<U, T>)
    explicit PersistentDynamicMonoidArray(const std::vector<U>& v) : PersistentDynamicMonoidArray() {
        pool->reserve(v.size());
        root = build_from_values(v, rng_state);
        pool->retain(root);
        pool->discard_unreferenced();
    }

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

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

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

    PersistentDynamicMonoidArray& operator=(const PersistentDynamicMonoidArray& 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;
    }

    PersistentDynamicMonoidArray& operator=(PersistentDynamicMonoidArray&& 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;
    }

    ~PersistentDynamicMonoidArray() {
        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; }

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

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

    PersistentDynamicMonoidArray 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);
    }

    PersistentDynamicMonoidArray 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);
    }

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

    PersistentDynamicMonoidArray insert(int pos, const PersistentDynamicMonoidArray& 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);
    }

    PersistentDynamicMonoidArray push_back(T value) const {
        return insert(size(), std::move(value));
    }

    PersistentDynamicMonoidArray push_front(T value) const {
        return insert(0, std::move(value));
    }

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

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

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

    PersistentDynamicMonoidArray 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);
    }

    PersistentDynamicMonoidArray 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);
    }

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

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

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

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

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

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

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

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

    PersistentDynamicMonoidArray 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);
    }

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

    PersistentDynamicMonoidArray 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);
    }

    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= size());
        if (l == r) return Monoid::id();
        return prod_dfs(root, l, r, 0);
    }

    T all_prod() const {
        return root == -1 ? Monoid::id() : (*pool)[root].prod;
    }

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

    PersistentDynamicMonoidArray 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_MONOID_ARRAY_HPP

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



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

#line 1 "monoid/concept.hpp"



#line 5 "monoid/concept.hpp"

namespace m1une {
namespace monoid {

// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
    // 1. Must define `value_type`
    typename M::value_type;

    // 2. Must have a static method `id()` returning `value_type`
    { M::id() } -> std::same_as<typename M::value_type>;

    // 3. Must have a static method `op(a, b)` returning `value_type`
    { M::op(a, b) } -> std::same_as<typename M::value_type>;
};

// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
    { M::inv(a) } -> std::same_as<typename M::value_type>;
};

// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;

}  // namespace monoid
}  // namespace m1une


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



#line 6 "ds/detail/persistent_binary_node_pool.hpp"
#include <deque>
#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 16 "ds/dynamic_array/persistent_dynamic_monoid_array.hpp"

namespace m1une {
namespace ds {

template <m1une::monoid::IsMonoid Monoid>
struct PersistentDynamicMonoidArray {
    using T = typename Monoid::value_type;

   private:
    struct Node {
        T val, prod, rprod;
        int priority;
        int count;
        int l, r;
        bool rev;

        Node(T value, T product, T reverse_product, int node_priority, int node_count, int left, int right,
             bool reversed)
            : val(std::move(value)),
              prod(std::move(product)),
              rprod(std::move(reverse_product)),
              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;
    }

    T node_prod(int t) const {
        return t == -1 ? Monoid::id() : (*pool)[t].prod;
    }

    T node_rprod(int t) const {
        return t == -1 ? Monoid::id() : (*pool)[t].rprod;
    }

    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);
    }

    template <typename U>
    static T make_value(const U& value) {
        if constexpr (requires(U x) { Monoid::make(x); }) {
            return Monoid::make(value);
        } else {
            return static_cast<T>(value);
        }
    }

    int make_node(T val, int priority, bool rev, int l, int r) const {
        T prod = Monoid::op(Monoid::op(node_prod(l), val), node_prod(r));
        T rprod = Monoid::op(Monoid::op(node_rprod(r), val), node_rprod(l));
        if (rev) std::swap(prod, rprod);
        int count = 1 + subtree_size(l) + subtree_size(r);
        return pool->emplace(std::move(val), std::move(prod), std::move(rprod), priority, count, l, r, rev);
    }

    int reversed_node(int t) const {
        if (t == -1) return -1;
        Node node = (*pool)[t];
        return make_node(std::move(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);
    }

    void pull(int t) const {
        Node& node = (*pool)[t];
        node.prod = Monoid::op(Monoid::op(node_prod(node.l), node.val), node_prod(node.r));
        node.rprod = Monoid::op(Monoid::op(node_rprod(node.r), node.val), node_rprod(node.l));
        if (node.rev) std::swap(node.prod, node.rprod);
    }

    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);
            }
        }
        pull(t);
        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;
    }

    T prod_dfs(int t, int ql, int qr, int offset, bool reversed = false) const {
        if (t == -1 || qr <= offset || offset + (*pool)[t].count <= ql) return Monoid::id();
        const Node& node = (*pool)[t];
        if (ql <= offset && offset + node.count <= qr) return reversed ? node.rprod : node.prod;
        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;
        T res = prod_dfs(l, ql, qr, offset, cur_reversed);
        if (ql <= node_pos && node_pos < qr) res = Monoid::op(res, node.val);
        return Monoid::op(res, prod_dfs(r, ql, qr, node_pos + 1, cur_reversed));
    }

    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);
    }

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

    int import_node(const PersistentDynamicMonoidArray& 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 PersistentDynamicMonoidArray(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);
    }

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

   public:
    PersistentDynamicMonoidArray()
        : 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 PersistentDynamicMonoidArray(int n) : PersistentDynamicMonoidArray(n, Monoid::id()) {}

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

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

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

    template <typename U>
        requires(!std::same_as<U, T>) && (requires(U x) { Monoid::make(x); } || std::convertible_to<U, T>)
    explicit PersistentDynamicMonoidArray(const std::vector<U>& v) : PersistentDynamicMonoidArray() {
        pool->reserve(v.size());
        root = build_from_values(v, rng_state);
        pool->retain(root);
        pool->discard_unreferenced();
    }

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

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

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

    PersistentDynamicMonoidArray& operator=(const PersistentDynamicMonoidArray& 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;
    }

    PersistentDynamicMonoidArray& operator=(PersistentDynamicMonoidArray&& 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;
    }

    ~PersistentDynamicMonoidArray() {
        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; }

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

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

    PersistentDynamicMonoidArray 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);
    }

    PersistentDynamicMonoidArray 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);
    }

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

    PersistentDynamicMonoidArray insert(int pos, const PersistentDynamicMonoidArray& 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);
    }

    PersistentDynamicMonoidArray push_back(T value) const {
        return insert(size(), std::move(value));
    }

    PersistentDynamicMonoidArray push_front(T value) const {
        return insert(0, std::move(value));
    }

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

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

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

    PersistentDynamicMonoidArray 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);
    }

    PersistentDynamicMonoidArray 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);
    }

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

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

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

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

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

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

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

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

    PersistentDynamicMonoidArray 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);
    }

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

    PersistentDynamicMonoidArray 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);
    }

    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= size());
        if (l == r) return Monoid::id();
        return prod_dfs(root, l, r, 0);
    }

    T all_prod() const {
        return root == -1 ? Monoid::id() : (*pool)[root].prod;
    }

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

    PersistentDynamicMonoidArray 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

Back to top page