Persistent Dynamic Segment Tree
(ds/segtree/persistent_dynamic_segtree.hpp)

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

Overview

m1une::ds::PersistentDynamicSegtree is a persistent sparse segment tree over a fixed integer coordinate domain. Point assignments return new versions while older versions remain available. It supports monoid range products and boundary searches without building the entire domain.

Every coordinate starts with the same initial_value. Products of untouched segments are derived from that leaf value, so a large uniform array can remain implicit. The default initial value is Monoid::id(), which gives the usual sparse-map behavior.

All related versions share immutable domain metadata and one contiguous node pool. Read-only queries do not allocate nodes. Products preserve coordinate order, so non-commutative monoids are supported. Nodes whose last parent or version reference disappears are recycled.

set_inplace mutates the current handle with copy-on-write. Shared nodes are cloned before modification and unique nodes are reused; all other live versions remain unchanged. set continues to return a distinct persistent version.

Template Parameters

Monoid: A type satisfying m1une::monoid::IsMonoid.
Index: A non-bool integral coordinate type. The default is long long.

The monoid must provide:

using value_type = T
static T id()
static T op(const T& a, const T& b)

Construction

PersistentDynamicSegtree(): creates an empty domain [0, 0).
PersistentDynamicSegtree(Index n): creates [0, n) with identity values.
PersistentDynamicSegtree(Index left, Index right): creates [left, right) with identity values.
PersistentDynamicSegtree(Index left, Index right, T initial_value): creates a domain with the specified uniform initial leaf.

Construction caches the possible untouched segment products at each depth. It uses $O(\log U)$ memory and $O(\log^2 U)$ monoid operations, where $U$ is the domain length. No tree node is allocated initially.

Methods

Method	Description	Complexity
`size_type size()`	Returns the unsigned domain length.	$O(1)$
`bool empty()`	Returns whether the domain is empty.	$O(1)$
`Index left_bound()`	Returns the left endpoint.	$O(1)$
`Index right_bound()`	Returns the right endpoint.	$O(1)$
`const T& initial_value()`	Returns the uniform initial leaf value.	$O(1)$
`void reserve(size_t n)`	Reserves shared-pool space for `n` nodes.	$O(K)$
`size_t node_count()`	Returns live nodes in the shared version family.	$O(1)$
`void release()`	Releases this root and resets the handle to the uniform initial version.	$O(F)$
`PersistentDynamicSegtree set(Index p, T x)`	Returns a version assigning `x` at `p`.	$O(\log U)$
`void set_inplace(Index p, T x)`	Assigns `x` in this version using copy-on-write.	$O(\log U)$
`T get(Index p)`	Returns the value at `p`.	$O(\log U)$
`T operator[](Index p)`	Equivalent to `get(p)`.	$O(\log U)$
`T prod(Index l, Index r)`	Returns the monoid product over `[l, r)`.	$O(\log U)$
`T all_prod()`	Returns the product over the entire domain.	$O(1)$
`Index max_right(Index l, F f)`	Finds the largest `r` for which `f(prod(l, r))` is true.	$O(\log U)$
`Index min_left(Index r, F f)`	Finds the smallest `l` for which `f(prod(l, r))` is true.	$O(\log U)$

Here $K$ is the number of live nodes and $F$ is the number freed by a release. Each assignment allocates $O(\log U)$ nodes in the worst case. Copying a version is $O(1)$. Destruction and assignment release roots automatically; freed slots are reused.

For max_right and min_left, the identity must satisfy the predicate and the predicate must be monotone along searched products.

Example

#include "ds/segtree/persistent_dynamic_segtree.hpp"
#include "monoid/add.hpp"

#include <iostream>

int main() {
    using Sum = m1une::monoid::Add<long long>;
    using Seg = m1une::ds::PersistentDynamicSegtree<Sum>;

    Seg base(-1'000'000'000LL, 1'000'000'001LL, 0);
    Seg first = base.set(-500'000'000LL, 7);
    Seg second = first.set(900'000'000LL, 11);

    std::cout << base.all_prod() << "\n";    // 0
    std::cout << first.all_prod() << "\n";   // 7
    std::cout << second.all_prod() << "\n";  // 18
    first.release();                         // second keeps shared nodes alive
}

Depends on

Verified with

Code

#ifndef M1UNE_PERSISTENT_DYNAMIC_SEGTREE_HPP
#define M1UNE_PERSISTENT_DYNAMIC_SEGTREE_HPP 1

#include <cassert>
#include <concepts>
#include <cstddef>
#include <limits>
#include <memory>
#include <numeric>
#include <type_traits>
#include <utility>
#include <vector>

#include "../../monoid/concept.hpp"
#include "dynamic_segtree_common.hpp"
#include "persistent_node_pool.hpp"

namespace m1une {
namespace ds {

// A persistent sparse segment tree over an integral half-open interval.
template <m1une::monoid::IsMonoid Monoid, std::integral Index = long long>
    requires(!std::same_as<std::remove_cv_t<Index>, bool>)
struct PersistentDynamicSegtree {
    using T = typename Monoid::value_type;
    using index_type = Index;
    using size_type = detail::dynamic_size_type<Index>;

   private:
    struct Node {
        T val;
        int left;
        int right;
        int references;

        Node() : val(Monoid::id()), left(0), right(0), references(0) {}
        explicit Node(T value) : val(std::move(value)), left(0), right(0), references(0) {}
    };

    struct Config {
        detail::UniformMonoidDomain<Monoid, Index> domain;

        Config(Index left, Index right, T initial_value) : domain(left, right, std::move(initial_value)) {}
    };

    std::shared_ptr<const Config> _config;
    using Pool = detail::PersistentNodePool<Node>;
    std::shared_ptr<Pool> _pool;
    int _root;

    PersistentDynamicSegtree(std::shared_ptr<const Config> config, std::shared_ptr<Pool> pool, int root)
        : _config(std::move(config)), _pool(std::move(pool)), _root(root) {
        _pool->retain(_root);
    }

    int new_node(T value) const { return _pool->emplace(std::move(value)); }

    const T& value(int t, Index left, Index right, int depth) const {
        if (t) return (*_pool)[t].val;
        return _config->domain.default_product(depth, left, right);
    }

    int set_node(int t, Index left, Index right, int depth, Index p, T x, bool copy_on_write = false) const {
        Index middle = std::midpoint(left, right);
        if (copy_on_write) {
            int result = t ? _pool->clone_if_shared(t) : new_node(value(0, left, right, depth));
            if (middle == left) {
                (*_pool)[result].val = std::move(x);
                return result;
            }
            int child;
            if (p < middle) {
                child = set_node((*_pool)[result].left, left, middle, depth + 1, p, std::move(x), true);
                _pool->replace((*_pool)[result].left, child);
            } else {
                child = set_node((*_pool)[result].right, middle, right, depth + 1, p, std::move(x), true);
                _pool->replace((*_pool)[result].right, child);
            }
            Node& node = (*_pool)[result];
            node.val = Monoid::op(value(node.left, left, middle, depth + 1),
                                  value(node.right, middle, right, depth + 1));
            return result;
        }
        if (middle == left) return new_node(std::move(x));

        int left_child = t ? (*_pool)[t].left : 0;
        int right_child = t ? (*_pool)[t].right : 0;
        if (p < middle) {
            left_child = set_node(left_child, left, middle, depth + 1, p, std::move(x));
        } else {
            right_child = set_node(right_child, middle, right, depth + 1, p, std::move(x));
        }

        int result = new_node(
            Monoid::op(value(left_child, left, middle, depth + 1), value(right_child, middle, right, depth + 1)));
        _pool->replace((*_pool)[result].left, left_child);
        _pool->replace((*_pool)[result].right, right_child);
        return result;
    }

    T prod_node(int t, Index left, Index right, int depth, Index query_left, Index query_right) const {
        if (query_right <= left || right <= query_left) return Monoid::id();
        if (query_left <= left && right <= query_right) {
            return value(t, left, right, depth);
        }
        Index middle = std::midpoint(left, right);
        return Monoid::op(prod_node(t ? (*_pool)[t].left : 0, left, middle, depth + 1, query_left, query_right),
                          prod_node(t ? (*_pool)[t].right : 0, middle, right, depth + 1, query_left, query_right));
    }

    template <class F>
    Index max_right_node(int t, Index left, Index right, int depth, Index query_left, T& product, F& predicate) const {
        if (right <= query_left) return right;
        if (query_left <= left) {
            T next = Monoid::op(product, value(t, left, right, depth));
            if (predicate(next)) {
                product = std::move(next);
                return right;
            }
            Index middle = std::midpoint(left, right);
            if (middle == left) return left;
        }

        Index middle = std::midpoint(left, right);
        Index result =
            max_right_node(t ? (*_pool)[t].left : 0, left, middle, depth + 1, query_left, product, predicate);
        if (result < middle) return result;
        return max_right_node(t ? (*_pool)[t].right : 0, middle, right, depth + 1, query_left, product, predicate);
    }

    template <class F>
    Index min_left_node(int t, Index left, Index right, int depth, Index query_right, T& product, F& predicate) const {
        if (query_right <= left) return left;
        if (right <= query_right) {
            T next = Monoid::op(value(t, left, right, depth), product);
            if (predicate(next)) {
                product = std::move(next);
                return left;
            }
            Index middle = std::midpoint(left, right);
            if (middle == left) return right;
        }

        Index middle = std::midpoint(left, right);
        Index result =
            min_left_node(t ? (*_pool)[t].right : 0, middle, right, depth + 1, query_right, product, predicate);
        if (middle < result) return result;
        return min_left_node(t ? (*_pool)[t].left : 0, left, middle, depth + 1, query_right, product, predicate);
    }

   public:
    PersistentDynamicSegtree() : PersistentDynamicSegtree(Index(0), Index(0), Monoid::id()) {}

    explicit PersistentDynamicSegtree(Index n) : PersistentDynamicSegtree(Index(0), n, Monoid::id()) {
        if constexpr (std::signed_integral<Index>) assert(Index(0) <= n);
    }

    PersistentDynamicSegtree(Index left, Index right) : PersistentDynamicSegtree(left, right, Monoid::id()) {}

    PersistentDynamicSegtree(Index left, Index right, T initial_value)
        : _config(std::make_shared<Config>(left, right, std::move(initial_value))),
          _pool(std::make_shared<Pool>()),
          _root(0) {}

    PersistentDynamicSegtree(const PersistentDynamicSegtree& other)
        : _config(other._config), _pool(other._pool), _root(other._root) {
        if (_pool) _pool->retain(_root);
    }
    PersistentDynamicSegtree(PersistentDynamicSegtree&& other) noexcept
        : _config(std::move(other._config)), _pool(std::move(other._pool)), _root(other._root) {
        other._root = 0;
    }
    PersistentDynamicSegtree& operator=(const PersistentDynamicSegtree& other) {
        if (this == &other) return *this;
        if (other._pool) other._pool->retain(other._root);
        if (_pool) _pool->release(_root);
        _config = other._config;
        _pool = other._pool;
        _root = other._root;
        return *this;
    }
    PersistentDynamicSegtree& operator=(PersistentDynamicSegtree&& other) noexcept {
        if (this == &other) return *this;
        if (_pool) _pool->release(_root);
        _config = std::move(other._config);
        _pool = std::move(other._pool);
        _root = other._root;
        other._root = 0;
        return *this;
    }
    ~PersistentDynamicSegtree() {
        if (_pool) _pool->release(_root);
    }

    size_type size() const { return _config->domain.size(); }

    bool empty() const { return _config->domain.empty(); }

    Index left_bound() const { return _config->domain.left_bound(); }

    Index right_bound() const { return _config->domain.right_bound(); }

    const T& initial_value() const { return _config->domain.initial_value(); }

    void reserve(std::size_t node_capacity) const {
        assert(node_capacity < std::numeric_limits<std::size_t>::max());
        _pool->reserve(node_capacity);
    }

    std::size_t node_count() const { return _pool->size(); }

    void release() {
        if (_pool) _pool->release(_root);
        _pool = std::make_shared<Pool>();
        _root = 0;
    }

    PersistentDynamicSegtree set(Index p, T x) const {
        assert(left_bound() <= p && p < right_bound());
        return PersistentDynamicSegtree(_config, _pool,
                                        set_node(_root, left_bound(), right_bound(), 0, p, std::move(x)));
    }

    void set_inplace(Index p, T x) {
        assert(left_bound() <= p && p < right_bound());
        int root = set_node(_root, left_bound(), right_bound(), 0, p, std::move(x), true);
        _pool->replace(_root, root);
    }

    T get(Index p) const {
        assert(left_bound() <= p && p < right_bound());
        int t = _root;
        Index left = left_bound();
        Index right = right_bound();

        while (t) {
            Index middle = std::midpoint(left, right);
            if (middle == left) return (*_pool)[t].val;
            if (p < middle) {
                t = (*_pool)[t].left;
                right = middle;
            } else {
                t = (*_pool)[t].right;
                left = middle;
            }
        }
        return initial_value();
    }

    T operator[](Index p) const { return get(p); }

    T prod(Index left, Index right) const {
        assert(left_bound() <= left && left <= right && right <= right_bound());
        if (left == right) return Monoid::id();
        return prod_node(_root, left_bound(), right_bound(), 0, left, right);
    }

    T all_prod() const { return value(_root, left_bound(), right_bound(), 0); }

    template <class F>
    Index max_right(Index left, F predicate) const {
        assert(left_bound() <= left && left <= right_bound());
        assert(predicate(Monoid::id()));
        if (left == right_bound()) return right_bound();
        T product = Monoid::id();
        return max_right_node(_root, left_bound(), right_bound(), 0, left, product, predicate);
    }

    template <class F>
    Index min_left(Index right, F predicate) const {
        assert(left_bound() <= right && right <= right_bound());
        assert(predicate(Monoid::id()));
        if (right == left_bound()) return left_bound();
        T product = Monoid::id();
        return min_left_node(_root, left_bound(), right_bound(), 0, right, product, predicate);
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_PERSISTENT_DYNAMIC_SEGTREE_HPP

#line 1 "ds/segtree/persistent_dynamic_segtree.hpp"



#include <cassert>
#include <concepts>
#include <cstddef>
#include <limits>
#include <memory>
#include <numeric>
#include <type_traits>
#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/segtree/dynamic_segtree_common.hpp"



#line 11 "ds/segtree/dynamic_segtree_common.hpp"

namespace m1une {
namespace ds {
namespace detail {

template <std::integral Index>
using dynamic_size_type = std::make_unsigned_t<Index>;

template <std::integral Index>
constexpr dynamic_size_type<Index> dynamic_distance(Index left, Index right) {
    return static_cast<dynamic_size_type<Index>>(right) - static_cast<dynamic_size_type<Index>>(left);
}

template <class Monoid, class Size>
typename Monoid::value_type monoid_repeat(typename Monoid::value_type value, Size count) {
    typename Monoid::value_type result = Monoid::id();
    while (count != 0) {
        if (count & 1) result = Monoid::op(result, value);
        count >>= 1;
        if (count != 0) value = Monoid::op(value, value);
    }
    return result;
}

template <class ActedMonoid>
typename ActedMonoid::value_type dynamic_mapping(
    const typename ActedMonoid::operator_type& f,
    const typename ActedMonoid::value_type& value
) {
    using F = typename ActedMonoid::operator_type;
    using T = typename ActedMonoid::value_type;
    if constexpr (requires(F g, T x, long long ord) { ActedMonoid::mapping(g, x, ord); }) {
        return ActedMonoid::mapping(f, value, 0);
    } else {
        return ActedMonoid::mapping(f, value);
    }
}

template <class ActedMonoid, class Size>
typename ActedMonoid::operator_type dynamic_shift(
    const typename ActedMonoid::operator_type& f,
    Size offset
) {
    using F = typename ActedMonoid::operator_type;
    if constexpr (requires(F g, long long ord) { ActedMonoid::op_shift(g, ord); }) {
        assert(offset <= static_cast<Size>(std::numeric_limits<long long>::max()));
        return ActedMonoid::op_shift(f, static_cast<long long>(offset));
    } else {
        return f;
    }
}

template <class Monoid, std::integral Index>
class UniformMonoidDomain {
   public:
    using T = typename Monoid::value_type;
    using size_type = dynamic_size_type<Index>;

   private:
    struct Level {
        size_type small_length;
        T small_value;
        T large_value;
    };

    Index _left;
    Index _right;
    T _initial_value;
    std::vector<Level> _levels;

   public:
    UniformMonoidDomain(Index left, Index right, T initial_value)
        : _left(left), _right(right), _initial_value(std::move(initial_value)) {
        assert(left <= right);
        size_type n = size();
        constexpr int digits = std::numeric_limits<size_type>::digits;
        _levels.reserve(digits + 1);
        for (int depth = 0; depth <= digits; depth++) {
            size_type small = depth == digits ? 0 : n >> depth;
            size_type large = small;
            if (depth != 0) {
                bool has_remainder;
                if (depth == digits) {
                    has_remainder = n != 0;
                } else {
                    size_type mask = (size_type(1) << depth) - 1;
                    has_remainder = (n & mask) != 0;
                }
                if (has_remainder) large++;
            }
            _levels.push_back(Level{
                small,
                monoid_repeat<Monoid>(_initial_value, small),
                monoid_repeat<Monoid>(_initial_value, large),
            });
        }
    }

    Index left_bound() const {
        return _left;
    }

    Index right_bound() const {
        return _right;
    }

    size_type size() const {
        return dynamic_distance(_left, _right);
    }

    bool empty() const {
        return _left == _right;
    }

    const T& initial_value() const {
        return _initial_value;
    }

    const T& default_product(int depth, Index left, Index right) const {
        assert(0 <= depth && depth < int(_levels.size()));
        const Level& level = _levels[depth];
        size_type length = dynamic_distance(left, right);
        if (length == level.small_length) return level.small_value;
        assert(length == level.small_length + 1);
        return level.large_value;
    }
};

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


#line 1 "ds/segtree/persistent_node_pool.hpp"



#line 9 "ds/segtree/persistent_node_pool.hpp"

namespace m1une {
namespace ds {
namespace detail {

// Node must have integer `left`, `right`, and `references` members.
template <class Node>
struct PersistentNodePool {
    std::vector<Node> nodes;
    int first_free = 0;
    std::size_t live_nodes = 0;

   private:
    void release_zero(int node) {
        int left = nodes[node].left;
        int right = nodes[node].right;
        nodes[node] = Node();
        nodes[node].left = first_free;
        first_free = node;
        --live_nodes;
        if (left && --nodes[left].references == 0) release_zero(left);
        if (right && --nodes[right].references == 0) release_zero(right);
    }

   public:
    PersistentNodePool() { nodes.emplace_back(); }

    void reserve(std::size_t capacity) { nodes.reserve(capacity + 1); }

    Node& operator[](int node) { return nodes[node]; }

    const Node& operator[](int node) const { return nodes[node]; }

    void retain(int node) {
        if (node) ++nodes[node].references;
    }

    void release(int node) {
        if (!node) return;
        assert(nodes[node].references > 0);
        if (--nodes[node].references == 0) release_zero(node);
    }

    template <class... Args>
    int emplace(Args&&... args) {
        int result;
        if (!first_free) {
            assert(nodes.size() < std::size_t(std::numeric_limits<int>::max()));
            nodes.emplace_back(std::forward<Args>(args)...);
            result = int(nodes.size()) - 1;
        } else {
            result = first_free;
            first_free = nodes[result].left;
            nodes[result] = Node(std::forward<Args>(args)...);
        }
        Node& node = nodes[result];
        node.references = 0;
        retain(node.left);
        retain(node.right);
        ++live_nodes;
        return result;
    }

    int clone(int node) {
        assert(node);
        Node copy = nodes[node];
        return emplace(std::move(copy));
    }

    bool unique(int node) const {
        return !node || nodes[node].references == 1;
    }

    // Returns node itself when it has one owner, otherwise an unowned clone.
    // The caller must attach a returned clone with replace() before it can be
    // released or exposed as a root.
    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);
    }

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

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


#line 17 "ds/segtree/persistent_dynamic_segtree.hpp"

namespace m1une {
namespace ds {

// A persistent sparse segment tree over an integral half-open interval.
template <m1une::monoid::IsMonoid Monoid, std::integral Index = long long>
    requires(!std::same_as<std::remove_cv_t<Index>, bool>)
struct PersistentDynamicSegtree {
    using T = typename Monoid::value_type;
    using index_type = Index;
    using size_type = detail::dynamic_size_type<Index>;

   private:
    struct Node {
        T val;
        int left;
        int right;
        int references;

        Node() : val(Monoid::id()), left(0), right(0), references(0) {}
        explicit Node(T value) : val(std::move(value)), left(0), right(0), references(0) {}
    };

    struct Config {
        detail::UniformMonoidDomain<Monoid, Index> domain;

        Config(Index left, Index right, T initial_value) : domain(left, right, std::move(initial_value)) {}
    };

    std::shared_ptr<const Config> _config;
    using Pool = detail::PersistentNodePool<Node>;
    std::shared_ptr<Pool> _pool;
    int _root;

    PersistentDynamicSegtree(std::shared_ptr<const Config> config, std::shared_ptr<Pool> pool, int root)
        : _config(std::move(config)), _pool(std::move(pool)), _root(root) {
        _pool->retain(_root);
    }

    int new_node(T value) const { return _pool->emplace(std::move(value)); }

    const T& value(int t, Index left, Index right, int depth) const {
        if (t) return (*_pool)[t].val;
        return _config->domain.default_product(depth, left, right);
    }

    int set_node(int t, Index left, Index right, int depth, Index p, T x, bool copy_on_write = false) const {
        Index middle = std::midpoint(left, right);
        if (copy_on_write) {
            int result = t ? _pool->clone_if_shared(t) : new_node(value(0, left, right, depth));
            if (middle == left) {
                (*_pool)[result].val = std::move(x);
                return result;
            }
            int child;
            if (p < middle) {
                child = set_node((*_pool)[result].left, left, middle, depth + 1, p, std::move(x), true);
                _pool->replace((*_pool)[result].left, child);
            } else {
                child = set_node((*_pool)[result].right, middle, right, depth + 1, p, std::move(x), true);
                _pool->replace((*_pool)[result].right, child);
            }
            Node& node = (*_pool)[result];
            node.val = Monoid::op(value(node.left, left, middle, depth + 1),
                                  value(node.right, middle, right, depth + 1));
            return result;
        }
        if (middle == left) return new_node(std::move(x));

        int left_child = t ? (*_pool)[t].left : 0;
        int right_child = t ? (*_pool)[t].right : 0;
        if (p < middle) {
            left_child = set_node(left_child, left, middle, depth + 1, p, std::move(x));
        } else {
            right_child = set_node(right_child, middle, right, depth + 1, p, std::move(x));
        }

        int result = new_node(
            Monoid::op(value(left_child, left, middle, depth + 1), value(right_child, middle, right, depth + 1)));
        _pool->replace((*_pool)[result].left, left_child);
        _pool->replace((*_pool)[result].right, right_child);
        return result;
    }

    T prod_node(int t, Index left, Index right, int depth, Index query_left, Index query_right) const {
        if (query_right <= left || right <= query_left) return Monoid::id();
        if (query_left <= left && right <= query_right) {
            return value(t, left, right, depth);
        }
        Index middle = std::midpoint(left, right);
        return Monoid::op(prod_node(t ? (*_pool)[t].left : 0, left, middle, depth + 1, query_left, query_right),
                          prod_node(t ? (*_pool)[t].right : 0, middle, right, depth + 1, query_left, query_right));
    }

    template <class F>
    Index max_right_node(int t, Index left, Index right, int depth, Index query_left, T& product, F& predicate) const {
        if (right <= query_left) return right;
        if (query_left <= left) {
            T next = Monoid::op(product, value(t, left, right, depth));
            if (predicate(next)) {
                product = std::move(next);
                return right;
            }
            Index middle = std::midpoint(left, right);
            if (middle == left) return left;
        }

        Index middle = std::midpoint(left, right);
        Index result =
            max_right_node(t ? (*_pool)[t].left : 0, left, middle, depth + 1, query_left, product, predicate);
        if (result < middle) return result;
        return max_right_node(t ? (*_pool)[t].right : 0, middle, right, depth + 1, query_left, product, predicate);
    }

    template <class F>
    Index min_left_node(int t, Index left, Index right, int depth, Index query_right, T& product, F& predicate) const {
        if (query_right <= left) return left;
        if (right <= query_right) {
            T next = Monoid::op(value(t, left, right, depth), product);
            if (predicate(next)) {
                product = std::move(next);
                return left;
            }
            Index middle = std::midpoint(left, right);
            if (middle == left) return right;
        }

        Index middle = std::midpoint(left, right);
        Index result =
            min_left_node(t ? (*_pool)[t].right : 0, middle, right, depth + 1, query_right, product, predicate);
        if (middle < result) return result;
        return min_left_node(t ? (*_pool)[t].left : 0, left, middle, depth + 1, query_right, product, predicate);
    }

   public:
    PersistentDynamicSegtree() : PersistentDynamicSegtree(Index(0), Index(0), Monoid::id()) {}

    explicit PersistentDynamicSegtree(Index n) : PersistentDynamicSegtree(Index(0), n, Monoid::id()) {
        if constexpr (std::signed_integral<Index>) assert(Index(0) <= n);
    }

    PersistentDynamicSegtree(Index left, Index right) : PersistentDynamicSegtree(left, right, Monoid::id()) {}

    PersistentDynamicSegtree(Index left, Index right, T initial_value)
        : _config(std::make_shared<Config>(left, right, std::move(initial_value))),
          _pool(std::make_shared<Pool>()),
          _root(0) {}

    PersistentDynamicSegtree(const PersistentDynamicSegtree& other)
        : _config(other._config), _pool(other._pool), _root(other._root) {
        if (_pool) _pool->retain(_root);
    }
    PersistentDynamicSegtree(PersistentDynamicSegtree&& other) noexcept
        : _config(std::move(other._config)), _pool(std::move(other._pool)), _root(other._root) {
        other._root = 0;
    }
    PersistentDynamicSegtree& operator=(const PersistentDynamicSegtree& other) {
        if (this == &other) return *this;
        if (other._pool) other._pool->retain(other._root);
        if (_pool) _pool->release(_root);
        _config = other._config;
        _pool = other._pool;
        _root = other._root;
        return *this;
    }
    PersistentDynamicSegtree& operator=(PersistentDynamicSegtree&& other) noexcept {
        if (this == &other) return *this;
        if (_pool) _pool->release(_root);
        _config = std::move(other._config);
        _pool = std::move(other._pool);
        _root = other._root;
        other._root = 0;
        return *this;
    }
    ~PersistentDynamicSegtree() {
        if (_pool) _pool->release(_root);
    }

    size_type size() const { return _config->domain.size(); }

    bool empty() const { return _config->domain.empty(); }

    Index left_bound() const { return _config->domain.left_bound(); }

    Index right_bound() const { return _config->domain.right_bound(); }

    const T& initial_value() const { return _config->domain.initial_value(); }

    void reserve(std::size_t node_capacity) const {
        assert(node_capacity < std::numeric_limits<std::size_t>::max());
        _pool->reserve(node_capacity);
    }

    std::size_t node_count() const { return _pool->size(); }

    void release() {
        if (_pool) _pool->release(_root);
        _pool = std::make_shared<Pool>();
        _root = 0;
    }

    PersistentDynamicSegtree set(Index p, T x) const {
        assert(left_bound() <= p && p < right_bound());
        return PersistentDynamicSegtree(_config, _pool,
                                        set_node(_root, left_bound(), right_bound(), 0, p, std::move(x)));
    }

    void set_inplace(Index p, T x) {
        assert(left_bound() <= p && p < right_bound());
        int root = set_node(_root, left_bound(), right_bound(), 0, p, std::move(x), true);
        _pool->replace(_root, root);
    }

    T get(Index p) const {
        assert(left_bound() <= p && p < right_bound());
        int t = _root;
        Index left = left_bound();
        Index right = right_bound();

        while (t) {
            Index middle = std::midpoint(left, right);
            if (middle == left) return (*_pool)[t].val;
            if (p < middle) {
                t = (*_pool)[t].left;
                right = middle;
            } else {
                t = (*_pool)[t].right;
                left = middle;
            }
        }
        return initial_value();
    }

    T operator[](Index p) const { return get(p); }

    T prod(Index left, Index right) const {
        assert(left_bound() <= left && left <= right && right <= right_bound());
        if (left == right) return Monoid::id();
        return prod_node(_root, left_bound(), right_bound(), 0, left, right);
    }

    T all_prod() const { return value(_root, left_bound(), right_bound(), 0); }

    template <class F>
    Index max_right(Index left, F predicate) const {
        assert(left_bound() <= left && left <= right_bound());
        assert(predicate(Monoid::id()));
        if (left == right_bound()) return right_bound();
        T product = Monoid::id();
        return max_right_node(_root, left_bound(), right_bound(), 0, left, product, predicate);
    }

    template <class F>
    Index min_left(Index right, F predicate) const {
        assert(left_bound() <= right && right <= right_bound());
        assert(predicate(Monoid::id()));
        if (right == left_bound()) return left_bound();
        T product = Monoid::id();
        return min_left_node(_root, left_bound(), right_bound(), 0, right, product, predicate);
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

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

Persistent Dynamic Segment Tree
(ds/segtree/persistent_dynamic_segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Verified with

Code

Persistent Dynamic Segment Tree (ds/segtree/persistent_dynamic_segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Verified with

Code

Persistent Dynamic Segment Tree
(ds/segtree/persistent_dynamic_segtree.hpp)