Rollback Dynamic Lazy Segment Tree
(ds/segtree/rollback_dynamic_lazy_segtree.hpp)

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

Overview

RollbackDynamicLazySegtree<ActedMonoid, Index> is a sparse lazy segment tree with point assignment, range actions, range products, and rollback over an integral half-open domain.

Methods

Constructors and read-only methods follow the corresponding mutable structure.

Method	Description	Complexity
`void clear()`	Resets the logical tree to its initial value.	$O(P)$ without snapshots; $O(1)$ with an active snapshot
`void set(Index pos, T value)`, `void set_inplace(Index pos, T value)`	Assigns one point.	$O(\log U)$
`void apply(Index pos, const F& f)`, `void apply(Index left, Index right, const F& f)`	Applies an action to a point or range.	$O(\log U)$
`void apply_inplace(...)`	Aliases of `apply`.	$O(\log U)$
`int snapshot()`	Registers the current state and returns its token.	$O(1)$
`int snapshot_count() const`	Returns the number of active snapshots.	$O(1)$
`void reserve_snapshots(int count)`	Reserves snapshot tokens.	$O(H)$
`void rollback(int state)`	Restores a current-path snapshot.	$O(F)$ total
`void clear_history()`, `void release()`	Releases saved states, or all materialized nodes.	$O(F)$

$U$ is the domain width, $P$ is the number of materialized nodes, and $F$ is the number of saved or newly allocated nodes discarded by the operation.

Snapshot semantics

Updates made before the first snapshot() retain no rollback data. A snapshot token is positive and valid only on the current path. rollback(state) restores that registered state, keeps it active, and invalidates newer snapshots. clear_history() commits the current state and invalidates every token. No per-update reversal operation is provided.

Within one snapshot interval, a materialized node is saved only before its first mutation; newly allocated nodes are truncated directly by rollback.

Example

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

using AM = m1une::acted_monoid::RangeAddRangeSum<long long>;
m1une::ds::RollbackDynamicLazySegtree<AM> seg(0, 100, AM::id());
int state = seg.snapshot();
seg.set(3, AM::make(2));
seg.apply(3, 4, 5);
seg.rollback(state);
assert(seg.get(3).sum == 0);

Depends on

Verified with

verify/ds/rollback_counterparts.test.cpp

Code

#ifndef M1UNE_DS_SEGTREE_ROLLBACK_DYNAMIC_LAZY_SEGTREE_HPP
#define M1UNE_DS_SEGTREE_ROLLBACK_DYNAMIC_LAZY_SEGTREE_HPP 1

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

#include "../../acted_monoid/concept.hpp"
#include "../detail/rollback_journal.hpp"
#include "dynamic_segtree_common.hpp"

namespace m1une {
namespace ds {

// A 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 RollbackDynamicLazySegtree {
    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;
        bool has_lazy;

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

    detail::UniformMonoidDomain<ActedMonoid, Index> _domain;
    detail::RollbackJournal<Node> _journal;

    int root() const { return _journal[0].left; }

    int new_node(Index left, Index right, int depth) {
        assert(_journal.nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        return _journal.emplace(_domain.default_product(depth, left, right));
    }

    const T& value(int t, Index left, Index right, int depth) const {
        if (t) return _journal[t].val;
        return _domain.default_product(depth, left, right);
    }

    void all_apply(int& t, Index left, Index right, int depth, const F& f) {
        if (!t) t = new_node(left, right, depth);
        _journal.touch(t);
        Node& node = _journal[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;
        }
    }

    void push(int t, Index left, Index right, int depth) {
        if (!_journal[t].has_lazy) return;
        Index middle = std::midpoint(left, right);
        if (middle == left) return;

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

        _journal.touch(t);
        Node& node = _journal[t];
        node.left = left_child;
        node.right = right_child;
        node.lazy = ActedMonoid::op_id();
        node.has_lazy = false;
    }

    void update(int t, Index left, Index right, int depth) {
        _journal.touch(t);
        Index middle = std::midpoint(left, right);
        _journal[t].val = ActedMonoid::op(
            value(_journal[t].left, left, middle, depth + 1),
            value(_journal[t].right, middle, right, depth + 1)
        );
    }

    int set_node(int t, Index left, Index right, int depth, Index p, T x) {
        if (!t) t = new_node(left, right, depth);
        Index middle = std::midpoint(left, right);
        if (middle == left) {
            _journal.touch(t);
            Node& node = _journal[t];
            node.val = std::move(x);
            node.lazy = ActedMonoid::op_id();
            node.has_lazy = false;
            return t;
        }

        push(t, left, right, depth);
        if (p < middle) {
            int child = set_node(_journal[t].left, left, middle, depth + 1, p, std::move(x));
            _journal.touch(t);
            _journal[t].left = child;
        } else {
            int child = set_node(_journal[t].right, middle, right, depth + 1, p, std::move(x));
            _journal.touch(t);
            _journal[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
    ) {
        if (query_right <= left || right <= query_left) return t;
        if (query_left <= left && right <= query_right) {
            all_apply(
                t,
                left,
                right,
                depth,
                detail::dynamic_shift<ActedMonoid>(f, detail::dynamic_distance(query_left, left))
            );
            return t;
        }

        if (!t) t = new_node(left, right, depth);
        push(t, left, right, depth);
        Index middle = std::midpoint(left, right);
        int left_child = apply_node(_journal[t].left, left, middle, depth + 1, query_left, query_right, f);
        int right_child = apply_node(_journal[t].right, middle, right, depth + 1, query_left, query_right, f);
        _journal.touch(t);
        _journal[t].left = left_child;
        _journal[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 || !_journal[t].has_lazy) return shifted;
        return ActedMonoid::op_comp(
            shifted,
            detail::dynamic_shift<ActedMonoid>(_journal[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 ? _journal[t].left : 0,
                left,
                middle,
                depth + 1,
                query_left,
                query_right,
                compose_for_child(inherited, t, 0)
            ),
            prod_node(
                t ? _journal[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 ? _journal[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 ? _journal[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 ? _journal[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 ? _journal[t].left : 0,
            left,
            middle,
            depth + 1,
            query_right,
            product,
            compose_for_child(inherited, t, 0),
            predicate
        );
    }

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

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

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

    RollbackDynamicLazySegtree(Index left, Index right, T initial_value)
        : _domain(left, right, std::move(initial_value)) {
        _journal.emplace(ActedMonoid::id());
    }

    size_type size() const {
        return _domain.size();
    }

    bool empty() const {
        return _domain.empty();
    }

    Index left_bound() const {
        return _domain.left_bound();
    }

    Index right_bound() const {
        return _domain.right_bound();
    }

    const T& initial_value() const {
        return _domain.initial_value();
    }

    void reserve(std::size_t node_capacity) {
        assert(node_capacity < std::numeric_limits<std::size_t>::max());
        _journal.nodes.reserve(node_capacity + 1);
        _journal.saved_epoch.reserve(node_capacity + 1);
    }

    std::size_t node_count() const {
        return _journal.nodes.size() - 1;
    }

    void clear() {
        if (_journal.snapshot_count() == 0) {
            _journal.clear();
            _journal.emplace(ActedMonoid::id());
            return;
        }
        _journal.touch(0);
        _journal[0].left = 0;
    }

    void set(Index p, T x) {
        assert(left_bound() <= p && p < right_bound());
        int next_root = set_node(root(), left_bound(), right_bound(), 0, p, std::move(x));
        if (next_root != root()) {
            _journal.touch(0);
            _journal[0].left = next_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);
    }

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

    void apply(Index left, Index right, const F& f) {
        assert(left_bound() <= left && left <= right && right <= right_bound());
        if (left == right) return;
        int next_root = apply_node(
            root(), left_bound(), right_bound(), 0, left, right, f
        );
        if (next_root != root()) {
            _journal.touch(0);
            _journal[0].left = next_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
        );
    }

    void set_inplace(Index p, T x) { set(p, std::move(x)); }
    void apply_inplace(Index p, const F& f) { apply(p, f); }
    void apply_inplace(Index left, Index right, const F& f) { apply(left, right, f); }

    int snapshot() { return _journal.snapshot(); }
    int snapshot_count() const { return _journal.snapshot_count(); }
    void reserve_snapshots(int count) { _journal.reserve_snapshots(count); }
    void rollback(int state) { _journal.rollback(state); }
    void clear_history() { _journal.clear_history(); }
    void release() { _journal.clear(); _journal.emplace(ActedMonoid::id()); }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DS_SEGTREE_ROLLBACK_DYNAMIC_LAZY_SEGTREE_HPP

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



#include <cassert>
#include <concepts>
#include <cstddef>
#include <limits>
#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/detail/rollback_journal.hpp"



#include <algorithm>
#line 7 "ds/detail/rollback_journal.hpp"
#include <cstdint>
#line 11 "ds/detail/rollback_journal.hpp"

namespace m1une {
namespace ds {
namespace detail {

template <class Node>
struct RollbackJournal {
    struct Change {
        int index;
        Node value;
    };

    struct Checkpoint {
        std::size_t change_size;
        std::size_t node_size;
        std::uint64_t epoch;
    };

    std::vector<Node> nodes;
    std::vector<Change> changes;
    std::vector<Checkpoint> checkpoints;
    std::vector<std::uint64_t> saved_epoch;
    std::uint64_t next_epoch = 1;

    std::uint64_t new_epoch() {
        if (next_epoch == 0) {
            std::fill(saved_epoch.begin(), saved_epoch.end(), 0);
            next_epoch = 1;
        }
        return next_epoch++;
    }

    int size() const { return int(nodes.size()); }

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

    template <class... Args>
    int emplace(Args&&... args) {
        assert(nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        int index = int(nodes.size());
        nodes.emplace_back(std::forward<Args>(args)...);
        saved_epoch.push_back(0);
        return index;
    }

    int snapshot() {
        assert(checkpoints.size() < std::size_t(std::numeric_limits<int>::max()));
        checkpoints.push_back(Checkpoint{changes.size(), nodes.size(), new_epoch()});
        return int(checkpoints.size());
    }

    void touch(int index) {
        assert(0 <= index && index < size());
        if (checkpoints.empty()) return;
        const Checkpoint& checkpoint = checkpoints.back();
        if (std::size_t(index) >= checkpoint.node_size) return;
        if (saved_epoch[index] == checkpoint.epoch) return;
        saved_epoch[index] = checkpoint.epoch;
        changes.push_back(Change{index, nodes[index]});
    }

    int snapshot_count() const { return int(checkpoints.size()); }

    void reserve_snapshots(int count) {
        assert(0 <= count);
        checkpoints.reserve(count);
    }

    void reserve_changes(std::size_t count) { changes.reserve(count); }

    void rollback(int state) {
        assert(1 <= state && state <= snapshot_count());
        Checkpoint checkpoint = checkpoints[state - 1];
        while (changes.size() > checkpoint.change_size) {
            Change change = std::move(changes.back());
            changes.pop_back();
            nodes[change.index] = std::move(change.value);
        }
        nodes.erase(nodes.begin() + checkpoint.node_size, nodes.end());
        saved_epoch.resize(checkpoint.node_size);
        checkpoints.resize(state);
        checkpoints.back().change_size = changes.size();
        checkpoints.back().node_size = nodes.size();
        checkpoints.back().epoch = new_epoch();
    }

    void clear_history() {
        changes.clear();
        checkpoints.clear();
        std::fill(saved_epoch.begin(), saved_epoch.end(), 0);
    }

    void clear() {
        nodes.clear();
        changes.clear();
        checkpoints.clear();
        saved_epoch.clear();
        next_epoch = 1;
    }
};

}  // namespace detail
}  // namespace ds
}  // 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 16 "ds/segtree/rollback_dynamic_lazy_segtree.hpp"

namespace m1une {
namespace ds {

// A 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 RollbackDynamicLazySegtree {
    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;
        bool has_lazy;

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

    detail::UniformMonoidDomain<ActedMonoid, Index> _domain;
    detail::RollbackJournal<Node> _journal;

    int root() const { return _journal[0].left; }

    int new_node(Index left, Index right, int depth) {
        assert(_journal.nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        return _journal.emplace(_domain.default_product(depth, left, right));
    }

    const T& value(int t, Index left, Index right, int depth) const {
        if (t) return _journal[t].val;
        return _domain.default_product(depth, left, right);
    }

    void all_apply(int& t, Index left, Index right, int depth, const F& f) {
        if (!t) t = new_node(left, right, depth);
        _journal.touch(t);
        Node& node = _journal[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;
        }
    }

    void push(int t, Index left, Index right, int depth) {
        if (!_journal[t].has_lazy) return;
        Index middle = std::midpoint(left, right);
        if (middle == left) return;

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

        _journal.touch(t);
        Node& node = _journal[t];
        node.left = left_child;
        node.right = right_child;
        node.lazy = ActedMonoid::op_id();
        node.has_lazy = false;
    }

    void update(int t, Index left, Index right, int depth) {
        _journal.touch(t);
        Index middle = std::midpoint(left, right);
        _journal[t].val = ActedMonoid::op(
            value(_journal[t].left, left, middle, depth + 1),
            value(_journal[t].right, middle, right, depth + 1)
        );
    }

    int set_node(int t, Index left, Index right, int depth, Index p, T x) {
        if (!t) t = new_node(left, right, depth);
        Index middle = std::midpoint(left, right);
        if (middle == left) {
            _journal.touch(t);
            Node& node = _journal[t];
            node.val = std::move(x);
            node.lazy = ActedMonoid::op_id();
            node.has_lazy = false;
            return t;
        }

        push(t, left, right, depth);
        if (p < middle) {
            int child = set_node(_journal[t].left, left, middle, depth + 1, p, std::move(x));
            _journal.touch(t);
            _journal[t].left = child;
        } else {
            int child = set_node(_journal[t].right, middle, right, depth + 1, p, std::move(x));
            _journal.touch(t);
            _journal[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
    ) {
        if (query_right <= left || right <= query_left) return t;
        if (query_left <= left && right <= query_right) {
            all_apply(
                t,
                left,
                right,
                depth,
                detail::dynamic_shift<ActedMonoid>(f, detail::dynamic_distance(query_left, left))
            );
            return t;
        }

        if (!t) t = new_node(left, right, depth);
        push(t, left, right, depth);
        Index middle = std::midpoint(left, right);
        int left_child = apply_node(_journal[t].left, left, middle, depth + 1, query_left, query_right, f);
        int right_child = apply_node(_journal[t].right, middle, right, depth + 1, query_left, query_right, f);
        _journal.touch(t);
        _journal[t].left = left_child;
        _journal[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 || !_journal[t].has_lazy) return shifted;
        return ActedMonoid::op_comp(
            shifted,
            detail::dynamic_shift<ActedMonoid>(_journal[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 ? _journal[t].left : 0,
                left,
                middle,
                depth + 1,
                query_left,
                query_right,
                compose_for_child(inherited, t, 0)
            ),
            prod_node(
                t ? _journal[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 ? _journal[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 ? _journal[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 ? _journal[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 ? _journal[t].left : 0,
            left,
            middle,
            depth + 1,
            query_right,
            product,
            compose_for_child(inherited, t, 0),
            predicate
        );
    }

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

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

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

    RollbackDynamicLazySegtree(Index left, Index right, T initial_value)
        : _domain(left, right, std::move(initial_value)) {
        _journal.emplace(ActedMonoid::id());
    }

    size_type size() const {
        return _domain.size();
    }

    bool empty() const {
        return _domain.empty();
    }

    Index left_bound() const {
        return _domain.left_bound();
    }

    Index right_bound() const {
        return _domain.right_bound();
    }

    const T& initial_value() const {
        return _domain.initial_value();
    }

    void reserve(std::size_t node_capacity) {
        assert(node_capacity < std::numeric_limits<std::size_t>::max());
        _journal.nodes.reserve(node_capacity + 1);
        _journal.saved_epoch.reserve(node_capacity + 1);
    }

    std::size_t node_count() const {
        return _journal.nodes.size() - 1;
    }

    void clear() {
        if (_journal.snapshot_count() == 0) {
            _journal.clear();
            _journal.emplace(ActedMonoid::id());
            return;
        }
        _journal.touch(0);
        _journal[0].left = 0;
    }

    void set(Index p, T x) {
        assert(left_bound() <= p && p < right_bound());
        int next_root = set_node(root(), left_bound(), right_bound(), 0, p, std::move(x));
        if (next_root != root()) {
            _journal.touch(0);
            _journal[0].left = next_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);
    }

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

    void apply(Index left, Index right, const F& f) {
        assert(left_bound() <= left && left <= right && right <= right_bound());
        if (left == right) return;
        int next_root = apply_node(
            root(), left_bound(), right_bound(), 0, left, right, f
        );
        if (next_root != root()) {
            _journal.touch(0);
            _journal[0].left = next_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
        );
    }

    void set_inplace(Index p, T x) { set(p, std::move(x)); }
    void apply_inplace(Index p, const F& f) { apply(p, f); }
    void apply_inplace(Index left, Index right, const F& f) { apply(left, right, f); }

    int snapshot() { return _journal.snapshot(); }
    int snapshot_count() const { return _journal.snapshot_count(); }
    void reserve_snapshots(int count) { _journal.reserve_snapshots(count); }
    void rollback(int state) { _journal.rollback(state); }
    void clear_history() { _journal.clear_history(); }
    void release() { _journal.clear(); _journal.emplace(ActedMonoid::id()); }
};

}  // namespace ds
}  // namespace m1une

m1une's library

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

Rollback Dynamic Lazy Segment Tree
(ds/segtree/rollback_dynamic_lazy_segtree.hpp)

Overview

Methods

Snapshot semantics

Example

Depends on

Verified with

Code

Rollback Dynamic Lazy Segment Tree (ds/segtree/rollback_dynamic_lazy_segtree.hpp)

Overview

Methods

Snapshot semantics

Example

Depends on

Verified with

Code

Rollback Dynamic Lazy Segment Tree
(ds/segtree/rollback_dynamic_lazy_segtree.hpp)