Beats Acted Monoid Concept
(beats_acted_monoid/concept.hpp)

• View this file on GitHub
• Last update: 2026-08-12 01:20:42+09:00
• Include: #include "beats_acted_monoid/concept.hpp"

Overview

m1une::beats_acted_monoid::IsBeatsActedMonoid<AM> extends m1une::acted_monoid::IsActedMonoid<AM> with:

static bool can_apply(
    const operator_type& f,
    const value_type& x
);

It is used by ds::SegtreeBeats. A true result promises that mapping(f, x) can update the whole represented segment. A false result requires descent and forbids both calling mapping at that node and composing f into its lazy tag. Every valid update must eventually be applicable at every real leaf. The identity operator must always be applicable and leave values unchanged.

op_comp(f, g) means applying g first, then f.

Optional three-argument can_apply and mapping overloads and optional op_shift are recognized by SegtreeBeats; they are not additional concept requirements.

Depends on

• Acted Monoid Concept (acted_monoid/concept.hpp)

Required by

• ds/segtree/persistent_segtree_beats.hpp
• Rollback Segment Tree Beats (ds/segtree/rollback_segtree_beats.hpp)
• Generic Segment Tree Beats! (ds/segtree/segtree_beats.hpp)

Verified with

• verify/beats_acted_monoid/range_bitwise_and_or_range_sum.test.cpp
• verify/beats_acted_monoid/range_bitwise_and_or_range_sum.test.cpp
• verify/beats_acted_monoid/range_chmin_chmax_add_range_sum.test.cpp
• verify/beats_acted_monoid/range_chmin_chmax_add_range_sum.test.cpp
• verify/ds/persistent_cow.test.cpp
• verify/ds/rollback_counterparts.test.cpp
• verify/ds/segtree/persistent_segtree_beats.test.cpp
• verify/ds/segtree/segtree_beats.test.cpp
• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_BEATS_ACTED_MONOID_CONCEPT_HPP
#define M1UNE_BEATS_ACTED_MONOID_CONCEPT_HPP 1

#include <concepts>

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

namespace m1une {
namespace beats_acted_monoid {

// An acted monoid whose action may require descent before it can be applied.
template <typename AM>
concept IsBeatsActedMonoid = m1une::acted_monoid::IsActedMonoid<AM> &&
    requires(typename AM::value_type x, typename AM::operator_type f) {
        { AM::can_apply(f, x) } -> std::same_as<bool>;
    };

}  // namespace beats_acted_monoid
}  // namespace m1une

#endif  // M1UNE_BEATS_ACTED_MONOID_CONCEPT_HPP

#line 1 "beats_acted_monoid/concept.hpp"



#include <concepts>

#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 7 "beats_acted_monoid/concept.hpp"

namespace m1une {
namespace beats_acted_monoid {

// An acted monoid whose action may require descent before it can be applied.
template <typename AM>
concept IsBeatsActedMonoid = m1une::acted_monoid::IsActedMonoid<AM> &&
    requires(typename AM::value_type x, typename AM::operator_type f) {
        { AM::can_apply(f, x) } -> std::same_as<bool>;
    };

}  // namespace beats_acted_monoid
}  // namespace m1une

Back to top page