Rollback Dual Segment Tree
(ds/segtree/rollback_dual_segtree.hpp)

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

Overview

RollbackDualSegtree<Monoid> supports range monoid actions, point assignment, point queries, and rollback. Monoid must satisfy m1une::monoid::IsMonoid; composition order matches DualSegtree.

Methods

Constructors and read-only methods follow DualSegtree<Monoid>.

Method	Description	Complexity
void set(int pos, T value), void set_inplace(int pos, T value)	Assigns one point.	$O(\log N)$
void apply(int pos, const T& value), void apply(int left, int right, const T& value)	Composes an action at a point or on [left, right).	$O(\log N)$
void apply_inplace(...)	Aliases of apply.	$O(\log N)$
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 states.	$O(F)$

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 tree node is saved only before its first mutation.

Example

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

using Add = m1une::monoid::Add<long long>;
m1une::ds::RollbackDualSegtree<Add> seg(4);
int state = seg.snapshot();
seg.apply(0, 3, 5);
seg.rollback(state);
assert(seg.get(1) == 0);

Depends on

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

Verified with

• verify/ds/rollback_counterparts.test.cpp

Code

#ifndef M1UNE_DS_SEGTREE_ROLLBACK_DUAL_SEGTREE_HPP
#define M1UNE_DS_SEGTREE_ROLLBACK_DUAL_SEGTREE_HPP 1

#include <algorithm>
#include <cassert>
#include <concepts>
#include <utility>
#include <vector>

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

namespace m1une {
namespace ds {

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

   private:
    struct Node {
        T value = Monoid::id();
        bool has_value = false;
    };

    int _n = 0;
    detail::RollbackJournal<Node> _journal;

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

    void initialize(int n) {
        assert(0 <= n);
        _n = n;
        _journal.nodes.assign(std::max(1, 4 * n), Node());
        _journal.saved_epoch.assign(_journal.nodes.size(), 0);
    }

    template <class U>
    void build(int node, int left, int right, const std::vector<U>& values) {
        if (right - left == 1) {
            _journal[node].value = make_value(values[left], left);
            _journal[node].has_value = true;
            return;
        }
        int middle = (left + right) >> 1;
        build(node << 1, left, middle, values);
        build(node << 1 | 1, middle, right, values);
    }

    void all_apply(int node, const T& value) {
        _journal.touch(node);
        Node& current = _journal[node];
        current.value = current.has_value
            ? Monoid::op(value, current.value)
            : value;
        current.has_value = true;
    }

    void push(int node) {
        if (!_journal[node].has_value) return;
        T value = _journal[node].value;
        all_apply(node << 1, value);
        all_apply(node << 1 | 1, value);
        _journal.touch(node);
        _journal[node].value = Monoid::id();
        _journal[node].has_value = false;
    }

    void set_node(int node, int left, int right, int pos, T value) {
        if (right - left == 1) {
            _journal.touch(node);
            _journal[node].value = std::move(value);
            _journal[node].has_value = true;
            return;
        }
        push(node);
        int middle = (left + right) >> 1;
        if (pos < middle) set_node(node << 1, left, middle, pos, std::move(value));
        else set_node(node << 1 | 1, middle, right, pos, std::move(value));
    }

    void apply_node(int node, int left, int right, int query_left, int query_right, const T& value) {
        if (query_right <= left || right <= query_left) return;
        if (query_left <= left && right <= query_right) {
            all_apply(node, value);
            return;
        }
        push(node);
        int middle = (left + right) >> 1;
        apply_node(node << 1, left, middle, query_left, query_right, value);
        apply_node(node << 1 | 1, middle, right, query_left, query_right, value);
    }

    T get_node(int node, int left, int right, int pos, T inherited) const {
        const Node& current = _journal[node];
        if (right - left == 1) {
            assert(current.has_value);
            return Monoid::op(inherited, current.value);
        }
        if (current.has_value) inherited = Monoid::op(inherited, current.value);
        int middle = (left + right) >> 1;
        if (pos < middle) return get_node(node << 1, left, middle, pos, std::move(inherited));
        return get_node(node << 1 | 1, middle, right, pos, std::move(inherited));
    }

   public:
    RollbackDualSegtree() { initialize(0); }
    explicit RollbackDualSegtree(int n) {
        initialize(n);
        if (n > 0) {
            std::vector<T> values(n, Monoid::id());
            build(1, 0, n, values);
        }
    }

    explicit RollbackDualSegtree(const std::vector<T>& values) {
        initialize(int(values.size()));
        if (_n > 0) build(1, 0, _n, values);
    }

    template <class U>
        requires(!std::same_as<U, T>)
    explicit RollbackDualSegtree(const std::vector<U>& values) {
        initialize(int(values.size()));
        if (_n > 0) build(1, 0, _n, values);
    }

    int size() const { return _n; }
    bool empty() const { return _n == 0; }
    std::size_t node_count() const { return _journal.nodes.size(); }

    void set(int pos, T value) {
        assert(0 <= pos && pos < _n);
        set_node(1, 0, _n, pos, std::move(value));
    }
    void set_inplace(int pos, T value) { set(pos, std::move(value)); }

    T get(int pos) const {
        assert(0 <= pos && pos < _n);
        return get_node(1, 0, _n, pos, Monoid::id());
    }
    T operator[](int pos) const { return get(pos); }

    void apply(int pos, const T& value) { apply(pos, pos + 1, value); }
    void apply(int left, int right, const T& value) {
        assert(0 <= left && left <= right && right <= _n);
        if (left != right) apply_node(1, 0, _n, left, right, value);
    }
    void apply_inplace(int pos, const T& value) { apply(pos, value); }
    void apply_inplace(int left, int right, const T& value) { apply(left, right, value); }

    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() { _n = 0; _journal.clear(); }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DS_SEGTREE_ROLLBACK_DUAL_SEGTREE_HPP

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



#include <algorithm>
#include <cassert>
#include <concepts>
#include <utility>
#include <vector>

#line 1 "monoid/concept.hpp"



#line 5 "monoid/concept.hpp"

namespace m1une {
namespace monoid {

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

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

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

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

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

}  // namespace monoid
}  // namespace m1une


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



#line 6 "ds/detail/rollback_journal.hpp"
#include <cstddef>
#include <cstdint>
#include <limits>
#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 12 "ds/segtree/rollback_dual_segtree.hpp"

namespace m1une {
namespace ds {

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

   private:
    struct Node {
        T value = Monoid::id();
        bool has_value = false;
    };

    int _n = 0;
    detail::RollbackJournal<Node> _journal;

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

    void initialize(int n) {
        assert(0 <= n);
        _n = n;
        _journal.nodes.assign(std::max(1, 4 * n), Node());
        _journal.saved_epoch.assign(_journal.nodes.size(), 0);
    }

    template <class U>
    void build(int node, int left, int right, const std::vector<U>& values) {
        if (right - left == 1) {
            _journal[node].value = make_value(values[left], left);
            _journal[node].has_value = true;
            return;
        }
        int middle = (left + right) >> 1;
        build(node << 1, left, middle, values);
        build(node << 1 | 1, middle, right, values);
    }

    void all_apply(int node, const T& value) {
        _journal.touch(node);
        Node& current = _journal[node];
        current.value = current.has_value
            ? Monoid::op(value, current.value)
            : value;
        current.has_value = true;
    }

    void push(int node) {
        if (!_journal[node].has_value) return;
        T value = _journal[node].value;
        all_apply(node << 1, value);
        all_apply(node << 1 | 1, value);
        _journal.touch(node);
        _journal[node].value = Monoid::id();
        _journal[node].has_value = false;
    }

    void set_node(int node, int left, int right, int pos, T value) {
        if (right - left == 1) {
            _journal.touch(node);
            _journal[node].value = std::move(value);
            _journal[node].has_value = true;
            return;
        }
        push(node);
        int middle = (left + right) >> 1;
        if (pos < middle) set_node(node << 1, left, middle, pos, std::move(value));
        else set_node(node << 1 | 1, middle, right, pos, std::move(value));
    }

    void apply_node(int node, int left, int right, int query_left, int query_right, const T& value) {
        if (query_right <= left || right <= query_left) return;
        if (query_left <= left && right <= query_right) {
            all_apply(node, value);
            return;
        }
        push(node);
        int middle = (left + right) >> 1;
        apply_node(node << 1, left, middle, query_left, query_right, value);
        apply_node(node << 1 | 1, middle, right, query_left, query_right, value);
    }

    T get_node(int node, int left, int right, int pos, T inherited) const {
        const Node& current = _journal[node];
        if (right - left == 1) {
            assert(current.has_value);
            return Monoid::op(inherited, current.value);
        }
        if (current.has_value) inherited = Monoid::op(inherited, current.value);
        int middle = (left + right) >> 1;
        if (pos < middle) return get_node(node << 1, left, middle, pos, std::move(inherited));
        return get_node(node << 1 | 1, middle, right, pos, std::move(inherited));
    }

   public:
    RollbackDualSegtree() { initialize(0); }
    explicit RollbackDualSegtree(int n) {
        initialize(n);
        if (n > 0) {
            std::vector<T> values(n, Monoid::id());
            build(1, 0, n, values);
        }
    }

    explicit RollbackDualSegtree(const std::vector<T>& values) {
        initialize(int(values.size()));
        if (_n > 0) build(1, 0, _n, values);
    }

    template <class U>
        requires(!std::same_as<U, T>)
    explicit RollbackDualSegtree(const std::vector<U>& values) {
        initialize(int(values.size()));
        if (_n > 0) build(1, 0, _n, values);
    }

    int size() const { return _n; }
    bool empty() const { return _n == 0; }
    std::size_t node_count() const { return _journal.nodes.size(); }

    void set(int pos, T value) {
        assert(0 <= pos && pos < _n);
        set_node(1, 0, _n, pos, std::move(value));
    }
    void set_inplace(int pos, T value) { set(pos, std::move(value)); }

    T get(int pos) const {
        assert(0 <= pos && pos < _n);
        return get_node(1, 0, _n, pos, Monoid::id());
    }
    T operator[](int pos) const { return get(pos); }

    void apply(int pos, const T& value) { apply(pos, pos + 1, value); }
    void apply(int left, int right, const T& value) {
        assert(0 <= left && left <= right && right <= _n);
        if (left != right) apply_node(1, 0, _n, left, right, value);
    }
    void apply_inplace(int pos, const T& value) { apply(pos, value); }
    void apply_inplace(int left, int right, const T& value) { apply(left, right, value); }

    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() { _n = 0; _journal.clear(); }
};

}  // namespace ds
}  // namespace m1une

Back to top page