Persistent Dynamic Lazy Segment Tree
(ds/segtree/persistent_dynamic_lazy_segtree.hpp)

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

Overview

m1une::ds::PersistentDynamicLazySegtree combines persistence, sparse allocation, and lazy propagation over a fixed integer coordinate domain. Assignments and range updates return new versions; previous versions remain queryable.

Every coordinate begins with one uniform initial_value. Untouched segment products are derived from that leaf without building the segment. For size-aware acted monoids, pass a real leaf value such as RangeAddRangeSum<long long>::make(0), not the empty-product identity.

All versions derived from one tree share a contiguous node pool and immutable domain metadata. Read-only queries allocate no nodes. Reference counting recycles nodes after their last parent or version handle is released.

set_inplace and apply_inplace mutate only the current handle using copy-on-write. Shared nodes, including children receiving a pushed lazy tag, are cloned before modification; unique nodes are reused. The ordinary updates still return new persistent versions.

Template Parameters

ActedMonoid: A type satisfying m1une::acted_monoid::IsActedMonoid.
Index: A non-bool integral coordinate type. The default is long long.

Position-dependent acted monoids may provide op_shift(f, offset). Existing shifted acted monoids accept long long, so applied interval lengths must fit in that type.

Construction

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

Construction uses $O(\log U)$ metadata and $O(\log^2 U)$ monoid operations to cache untouched products, 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.	$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)$
`PersistentDynamicLazySegtree 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 product over `[l, r)`.	$O(\log U)$
`T all_prod()`	Returns the product over the entire domain.	$O(1)$
`PersistentDynamicLazySegtree apply(Index p, F f)`	Returns a version applying `f` at `p`.	$O(\log U)$
`PersistentDynamicLazySegtree apply(Index l, Index r, F f)`	Returns a version applying `f` over `[l, r)`.	$O(\log U)$
`void apply_inplace(Index p, const F& f)`	Applies `f` at `p` in this version using copy-on-write.	$O(\log U)$
`void apply_inplace(Index l, Index r, const F& f)`	Applies `f` over `[l, r)` in this version using copy-on-write.	$O(\log U)$
`Index max_right(Index l, G g)`	Finds the largest valid right boundary.	$O(\log U)$
`Index min_left(Index r, G g)`	Finds the smallest valid left boundary.	$O(\log U)$

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

Example

#include "acted_monoid/range_add_range_sum.hpp"
#include "ds/segtree/persistent_dynamic_lazy_segtree.hpp"

#include <iostream>

int main() {
    using AM = m1une::acted_monoid::RangeAddRangeSum<long long>;
    using Seg = m1une::ds::PersistentDynamicLazySegtree<AM>;

    Seg base(-1'000'000'000LL, 1'000'000'001LL, AM::make(0));
    Seg first = base.apply(-10, 20, 5);
    Seg second = first.set(0, AM::make(100));

    std::cout << base.all_prod().sum << "\n";    // 0
    std::cout << first.all_prod().sum << "\n";   // 150
    std::cout << second.all_prod().sum << "\n";  // 245
    first.release();                             // drop an unneeded root early
}

Depends on

Verified with

Code

#ifndef M1UNE_PERSISTENT_DYNAMIC_LAZY_SEGTREE_HPP
#define M1UNE_PERSISTENT_DYNAMIC_LAZY_SEGTREE_HPP 1

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

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

namespace m1une {
namespace ds {

// A persistent sparse lazy segment tree over an integral half-open interval.
template <m1une::acted_monoid::IsActedMonoid ActedMonoid, std::integral Index = long long>
    requires(!std::same_as<std::remove_cv_t<Index>, bool>)
struct PersistentDynamicLazySegtree {
    using T = typename ActedMonoid::value_type;
    using F = typename ActedMonoid::operator_type;
    using index_type = Index;
    using size_type = detail::dynamic_size_type<Index>;

   private:
    struct Node {
        T val;
        F lazy;
        int left;
        int right;
        int references;
        bool has_lazy;

        Node()
            : val(ActedMonoid::id()), lazy(ActedMonoid::op_id()), left(0), right(0), references(0), has_lazy(false) {}
        explicit Node(T value)
            : val(std::move(value)), lazy(ActedMonoid::op_id()), left(0), right(0), references(0), has_lazy(false) {}
    };

    struct Config {
        detail::UniformMonoidDomain<ActedMonoid, 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;

    PersistentDynamicLazySegtree(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(Index left, Index right, int depth) const {
        return _pool->emplace(_config->domain.default_product(depth, left, right));
    }

    int clone_or_new(int t, Index left, Index right, int depth, bool copy_on_write = false) const {
        if (!t) return new_node(left, right, depth);
        return copy_on_write ? _pool->clone_if_shared(t) : _pool->clone(t);
    }

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

    void all_apply_to_node(int t, Index left, Index right, const F& f) const {
        Node& node = (*_pool)[t];
        node.val = detail::dynamic_mapping<ActedMonoid>(f, node.val);
        if (std::midpoint(left, right) != left) {
            node.lazy = ActedMonoid::op_comp(f, node.lazy);
            node.has_lazy = true;
        }
    }

    int all_apply_clone(int t, Index left, Index right, int depth, const F& f,
                        bool copy_on_write = false) const {
        int result = clone_or_new(t, left, right, depth, copy_on_write);
        all_apply_to_node(result, left, right, f);
        return result;
    }

    void push(int t, Index left, Index right, int depth, bool copy_on_write = false) const {
        if (!(*_pool)[t].has_lazy) return;
        Index middle = std::midpoint(left, right);
        if (middle == left) return;

        F lazy = (*_pool)[t].lazy;
        int left_child = all_apply_clone((*_pool)[t].left, left, middle, depth + 1, lazy, copy_on_write);
        int right_child =
            all_apply_clone((*_pool)[t].right, middle, right, depth + 1,
                            detail::dynamic_shift<ActedMonoid>(lazy, detail::dynamic_distance(left, middle)),
                            copy_on_write);

        Node& node = (*_pool)[t];
        _pool->replace(node.left, left_child);
        _pool->replace(node.right, right_child);
        node.lazy = ActedMonoid::op_id();
        node.has_lazy = false;
    }

    void update(int t, Index left, Index right, int depth) const {
        Index middle = std::midpoint(left, right);
        Node& node = (*_pool)[t];
        node.val =
            ActedMonoid::op(value(node.left, left, middle, depth + 1), value(node.right, middle, right, depth + 1));
    }

    int set_node(int t, Index left, Index right, int depth, Index p, T x,
                 bool copy_on_write = false) const {
        t = clone_or_new(t, left, right, depth, copy_on_write);
        Index middle = std::midpoint(left, right);
        if (middle == left) {
            Node& node = (*_pool)[t];
            node.val = std::move(x);
            node.lazy = ActedMonoid::op_id();
            node.has_lazy = false;
            return t;
        }

        push(t, left, right, depth, copy_on_write);
        if (p < middle) {
            int child = set_node((*_pool)[t].left, left, middle, depth + 1, p, std::move(x), copy_on_write);
            _pool->replace((*_pool)[t].left, child);
        } else {
            int child = set_node((*_pool)[t].right, middle, right, depth + 1, p, std::move(x), copy_on_write);
            _pool->replace((*_pool)[t].right, child);
        }
        update(t, left, right, depth);
        return t;
    }

    int apply_node(int t, Index left, Index right, int depth, Index query_left, Index query_right, const F& f,
                   bool copy_on_write = false) const {
        if (query_right <= left || right <= query_left) return t;
        if (query_left <= left && right <= query_right) {
            return all_apply_clone(t, left, right, depth,
                                   detail::dynamic_shift<ActedMonoid>(f, detail::dynamic_distance(query_left, left)),
                                   copy_on_write);
        }

        t = clone_or_new(t, left, right, depth, copy_on_write);
        push(t, left, right, depth, copy_on_write);
        Index middle = std::midpoint(left, right);
        int left_child = apply_node((*_pool)[t].left, left, middle, depth + 1, query_left, query_right, f,
                                    copy_on_write);
        int right_child = apply_node((*_pool)[t].right, middle, right, depth + 1, query_left, query_right, f,
                                     copy_on_write);
        _pool->replace((*_pool)[t].left, left_child);
        _pool->replace((*_pool)[t].right, right_child);
        update(t, left, right, depth);
        return t;
    }

    F compose_for_child(const F& inherited, int t, size_type offset) const {
        F shifted = detail::dynamic_shift<ActedMonoid>(inherited, offset);
        if (!t || !(*_pool)[t].has_lazy) return shifted;
        return ActedMonoid::op_comp(shifted, detail::dynamic_shift<ActedMonoid>((*_pool)[t].lazy, offset));
    }

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

    template <class G>
    Index max_right_node(int t, Index left, Index right, int depth, Index query_left, T& product, const F& inherited,
                         G& predicate) const {
        if (right <= query_left) return right;
        if (query_left <= left) {
            T next =
                ActedMonoid::op(product, detail::dynamic_mapping<ActedMonoid>(inherited, 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,
                                      compose_for_child(inherited, t, 0), predicate);
        if (result < middle) return result;
        return max_right_node(t ? (*_pool)[t].right : 0, middle, right, depth + 1, query_left, product,
                              compose_for_child(inherited, t, detail::dynamic_distance(left, middle)), predicate);
    }

    template <class G>
    Index min_left_node(int t, Index left, Index right, int depth, Index query_right, T& product, const F& inherited,
                        G& predicate) const {
        if (query_right <= left) return left;
        if (right <= query_right) {
            T next =
                ActedMonoid::op(detail::dynamic_mapping<ActedMonoid>(inherited, 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,
                          compose_for_child(inherited, t, detail::dynamic_distance(left, middle)), predicate);
        if (middle < result) return result;
        return min_left_node(t ? (*_pool)[t].left : 0, left, middle, depth + 1, query_right, product,
                             compose_for_child(inherited, t, 0), predicate);
    }

   public:
    PersistentDynamicLazySegtree() : PersistentDynamicLazySegtree(Index(0), Index(0), ActedMonoid::id()) {}

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

    PersistentDynamicLazySegtree(Index left, Index right)
        : PersistentDynamicLazySegtree(left, right, ActedMonoid::id()) {}

    PersistentDynamicLazySegtree(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) {}

    PersistentDynamicLazySegtree(const PersistentDynamicLazySegtree& other)
        : _config(other._config), _pool(other._pool), _root(other._root) {
        if (_pool) _pool->retain(_root);
    }
    PersistentDynamicLazySegtree(PersistentDynamicLazySegtree&& other) noexcept
        : _config(std::move(other._config)), _pool(std::move(other._pool)), _root(other._root) {
        other._root = 0;
    }
    PersistentDynamicLazySegtree& operator=(const PersistentDynamicLazySegtree& 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;
    }
    PersistentDynamicLazySegtree& operator=(PersistentDynamicLazySegtree&& 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;
    }
    ~PersistentDynamicLazySegtree() {
        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;
    }

    PersistentDynamicLazySegtree set(Index p, T x) const {
        assert(left_bound() <= p && p < right_bound());
        return PersistentDynamicLazySegtree(_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());
        return prod(p, p + 1);
    }

    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 ActedMonoid::id();
        return prod_node(_root, left_bound(), right_bound(), 0, left, right, ActedMonoid::op_id());
    }

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

    PersistentDynamicLazySegtree apply(Index p, const F& f) const {
        assert(left_bound() <= p && p < right_bound());
        return apply(p, p + 1, f);
    }

    PersistentDynamicLazySegtree apply(Index left, Index right, const F& f) const {
        assert(left_bound() <= left && left <= right && right <= right_bound());
        if (left == right) return *this;
        return PersistentDynamicLazySegtree(_config, _pool,
                                            apply_node(_root, left_bound(), right_bound(), 0, left, right, f));
    }

    void apply_inplace(Index p, const F& f) {
        assert(left_bound() <= p && p < right_bound());
        apply_inplace(p, p + 1, f);
    }

    void apply_inplace(Index left, Index right, const F& f) {
        assert(left_bound() <= left && left <= right && right <= right_bound());
        if (left == right) return;
        int root = apply_node(_root, left_bound(), right_bound(), 0, left, right, f, true);
        _pool->replace(_root, root);
    }

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

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

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_PERSISTENT_DYNAMIC_LAZY_SEGTREE_HPP

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



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

#line 1 "acted_monoid/concept.hpp"



#line 5 "acted_monoid/concept.hpp"

namespace m1une {
namespace acted_monoid {

// Concept defining the requirements for an Acted Monoid.
template <typename AM>
concept IsActedMonoid = requires(typename AM::value_type a, typename AM::value_type b, typename AM::operator_type f,
                                 typename AM::operator_type g) {
    // 1. Value Monoid
    typename AM::value_type;
    { AM::id() } -> std::same_as<typename AM::value_type>;
    { AM::op(a, b) } -> std::same_as<typename AM::value_type>;

    // 2. Operator Monoid
    typename AM::operator_type;
    { AM::op_id() } -> std::same_as<typename AM::operator_type>;
    { AM::op_comp(f, g) } -> std::same_as<typename AM::operator_type>;  // Composition order: f(g(x))

    // 3. Mapping: Operator x Value -> Value
    { AM::mapping(f, a) } -> std::same_as<typename AM::value_type>;
};

// Concept for acted monoids whose value monoid is a commutative group.
// The value operation must obey commutativity and inverse laws.
template <typename AM>
concept IsCommutativeActedGroup = IsActedMonoid<AM> && requires(typename AM::value_type a) {
    { AM::inv(a) } -> std::same_as<typename AM::value_type>;
};

}  // namespace acted_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_lazy_segtree.hpp"

namespace m1une {
namespace ds {

// A persistent sparse lazy segment tree over an integral half-open interval.
template <m1une::acted_monoid::IsActedMonoid ActedMonoid, std::integral Index = long long>
    requires(!std::same_as<std::remove_cv_t<Index>, bool>)
struct PersistentDynamicLazySegtree {
    using T = typename ActedMonoid::value_type;
    using F = typename ActedMonoid::operator_type;
    using index_type = Index;
    using size_type = detail::dynamic_size_type<Index>;

   private:
    struct Node {
        T val;
        F lazy;
        int left;
        int right;
        int references;
        bool has_lazy;

        Node()
            : val(ActedMonoid::id()), lazy(ActedMonoid::op_id()), left(0), right(0), references(0), has_lazy(false) {}
        explicit Node(T value)
            : val(std::move(value)), lazy(ActedMonoid::op_id()), left(0), right(0), references(0), has_lazy(false) {}
    };

    struct Config {
        detail::UniformMonoidDomain<ActedMonoid, 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;

    PersistentDynamicLazySegtree(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(Index left, Index right, int depth) const {
        return _pool->emplace(_config->domain.default_product(depth, left, right));
    }

    int clone_or_new(int t, Index left, Index right, int depth, bool copy_on_write = false) const {
        if (!t) return new_node(left, right, depth);
        return copy_on_write ? _pool->clone_if_shared(t) : _pool->clone(t);
    }

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

    void all_apply_to_node(int t, Index left, Index right, const F& f) const {
        Node& node = (*_pool)[t];
        node.val = detail::dynamic_mapping<ActedMonoid>(f, node.val);
        if (std::midpoint(left, right) != left) {
            node.lazy = ActedMonoid::op_comp(f, node.lazy);
            node.has_lazy = true;
        }
    }

    int all_apply_clone(int t, Index left, Index right, int depth, const F& f,
                        bool copy_on_write = false) const {
        int result = clone_or_new(t, left, right, depth, copy_on_write);
        all_apply_to_node(result, left, right, f);
        return result;
    }

    void push(int t, Index left, Index right, int depth, bool copy_on_write = false) const {
        if (!(*_pool)[t].has_lazy) return;
        Index middle = std::midpoint(left, right);
        if (middle == left) return;

        F lazy = (*_pool)[t].lazy;
        int left_child = all_apply_clone((*_pool)[t].left, left, middle, depth + 1, lazy, copy_on_write);
        int right_child =
            all_apply_clone((*_pool)[t].right, middle, right, depth + 1,
                            detail::dynamic_shift<ActedMonoid>(lazy, detail::dynamic_distance(left, middle)),
                            copy_on_write);

        Node& node = (*_pool)[t];
        _pool->replace(node.left, left_child);
        _pool->replace(node.right, right_child);
        node.lazy = ActedMonoid::op_id();
        node.has_lazy = false;
    }

    void update(int t, Index left, Index right, int depth) const {
        Index middle = std::midpoint(left, right);
        Node& node = (*_pool)[t];
        node.val =
            ActedMonoid::op(value(node.left, left, middle, depth + 1), value(node.right, middle, right, depth + 1));
    }

    int set_node(int t, Index left, Index right, int depth, Index p, T x,
                 bool copy_on_write = false) const {
        t = clone_or_new(t, left, right, depth, copy_on_write);
        Index middle = std::midpoint(left, right);
        if (middle == left) {
            Node& node = (*_pool)[t];
            node.val = std::move(x);
            node.lazy = ActedMonoid::op_id();
            node.has_lazy = false;
            return t;
        }

        push(t, left, right, depth, copy_on_write);
        if (p < middle) {
            int child = set_node((*_pool)[t].left, left, middle, depth + 1, p, std::move(x), copy_on_write);
            _pool->replace((*_pool)[t].left, child);
        } else {
            int child = set_node((*_pool)[t].right, middle, right, depth + 1, p, std::move(x), copy_on_write);
            _pool->replace((*_pool)[t].right, child);
        }
        update(t, left, right, depth);
        return t;
    }

    int apply_node(int t, Index left, Index right, int depth, Index query_left, Index query_right, const F& f,
                   bool copy_on_write = false) const {
        if (query_right <= left || right <= query_left) return t;
        if (query_left <= left && right <= query_right) {
            return all_apply_clone(t, left, right, depth,
                                   detail::dynamic_shift<ActedMonoid>(f, detail::dynamic_distance(query_left, left)),
                                   copy_on_write);
        }

        t = clone_or_new(t, left, right, depth, copy_on_write);
        push(t, left, right, depth, copy_on_write);
        Index middle = std::midpoint(left, right);
        int left_child = apply_node((*_pool)[t].left, left, middle, depth + 1, query_left, query_right, f,
                                    copy_on_write);
        int right_child = apply_node((*_pool)[t].right, middle, right, depth + 1, query_left, query_right, f,
                                     copy_on_write);
        _pool->replace((*_pool)[t].left, left_child);
        _pool->replace((*_pool)[t].right, right_child);
        update(t, left, right, depth);
        return t;
    }

    F compose_for_child(const F& inherited, int t, size_type offset) const {
        F shifted = detail::dynamic_shift<ActedMonoid>(inherited, offset);
        if (!t || !(*_pool)[t].has_lazy) return shifted;
        return ActedMonoid::op_comp(shifted, detail::dynamic_shift<ActedMonoid>((*_pool)[t].lazy, offset));
    }

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

    template <class G>
    Index max_right_node(int t, Index left, Index right, int depth, Index query_left, T& product, const F& inherited,
                         G& predicate) const {
        if (right <= query_left) return right;
        if (query_left <= left) {
            T next =
                ActedMonoid::op(product, detail::dynamic_mapping<ActedMonoid>(inherited, 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,
                                      compose_for_child(inherited, t, 0), predicate);
        if (result < middle) return result;
        return max_right_node(t ? (*_pool)[t].right : 0, middle, right, depth + 1, query_left, product,
                              compose_for_child(inherited, t, detail::dynamic_distance(left, middle)), predicate);
    }

    template <class G>
    Index min_left_node(int t, Index left, Index right, int depth, Index query_right, T& product, const F& inherited,
                        G& predicate) const {
        if (query_right <= left) return left;
        if (right <= query_right) {
            T next =
                ActedMonoid::op(detail::dynamic_mapping<ActedMonoid>(inherited, 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,
                          compose_for_child(inherited, t, detail::dynamic_distance(left, middle)), predicate);
        if (middle < result) return result;
        return min_left_node(t ? (*_pool)[t].left : 0, left, middle, depth + 1, query_right, product,
                             compose_for_child(inherited, t, 0), predicate);
    }

   public:
    PersistentDynamicLazySegtree() : PersistentDynamicLazySegtree(Index(0), Index(0), ActedMonoid::id()) {}

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

    PersistentDynamicLazySegtree(Index left, Index right)
        : PersistentDynamicLazySegtree(left, right, ActedMonoid::id()) {}

    PersistentDynamicLazySegtree(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) {}

    PersistentDynamicLazySegtree(const PersistentDynamicLazySegtree& other)
        : _config(other._config), _pool(other._pool), _root(other._root) {
        if (_pool) _pool->retain(_root);
    }
    PersistentDynamicLazySegtree(PersistentDynamicLazySegtree&& other) noexcept
        : _config(std::move(other._config)), _pool(std::move(other._pool)), _root(other._root) {
        other._root = 0;
    }
    PersistentDynamicLazySegtree& operator=(const PersistentDynamicLazySegtree& 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;
    }
    PersistentDynamicLazySegtree& operator=(PersistentDynamicLazySegtree&& 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;
    }
    ~PersistentDynamicLazySegtree() {
        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;
    }

    PersistentDynamicLazySegtree set(Index p, T x) const {
        assert(left_bound() <= p && p < right_bound());
        return PersistentDynamicLazySegtree(_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());
        return prod(p, p + 1);
    }

    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 ActedMonoid::id();
        return prod_node(_root, left_bound(), right_bound(), 0, left, right, ActedMonoid::op_id());
    }

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

    PersistentDynamicLazySegtree apply(Index p, const F& f) const {
        assert(left_bound() <= p && p < right_bound());
        return apply(p, p + 1, f);
    }

    PersistentDynamicLazySegtree apply(Index left, Index right, const F& f) const {
        assert(left_bound() <= left && left <= right && right <= right_bound());
        if (left == right) return *this;
        return PersistentDynamicLazySegtree(_config, _pool,
                                            apply_node(_root, left_bound(), right_bound(), 0, left, right, f));
    }

    void apply_inplace(Index p, const F& f) {
        assert(left_bound() <= p && p < right_bound());
        apply_inplace(p, p + 1, f);
    }

    void apply_inplace(Index left, Index right, const F& f) {
        assert(left_bound() <= left && left <= right && right <= right_bound());
        if (left == right) return;
        int root = apply_node(_root, left_bound(), right_bound(), 0, left, right, f, true);
        _pool->replace(_root, root);
    }

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

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

}  // namespace ds
}  // namespace m1une

m1une's library

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

Persistent Dynamic Lazy Segment Tree
(ds/segtree/persistent_dynamic_lazy_segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Verified with

Code

Persistent Dynamic Lazy Segment Tree (ds/segtree/persistent_dynamic_lazy_segtree.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Verified with

Code

Persistent Dynamic Lazy Segment Tree
(ds/segtree/persistent_dynamic_lazy_segtree.hpp)