Acted Monoid Concept
(acted_monoid/concept.hpp)

• View this file on GitHub
• Last update: 2026-06-17 21:06:48+09:00
• Include: #include "acted_monoid/concept.hpp"

Overview

m1une::acted_monoid::IsActedMonoid is the C++20 concept used by lazy propagation data structures such as LazySegtree.

An acted monoid has three parts:

1. A value monoid, which combines segment values for queries.
2. An operator monoid, which combines lazy update operations.
3. A mapping function, which applies one operator to one value.

For example, in range-add range-sum:

• the value stores (sum, size),
• the lazy operator stores the amount to add,
• mapping(add, value) increases the sum by add * size.

Requirements

The concept requires the type to implement these members:

• using value_type The type stored for each segment.

• using operator_type The type stored for each lazy operation.

• static value_type id() Returns the identity element of the value monoid.

• static value_type op(const value_type& a, const value_type& b) Combines two segment values.

• static operator_type op_id() Returns the identity operation.

• static operator_type op_comp(const operator_type& f, const operator_type& g) Composes two operators. The order is f(g(x)): apply g first, then f.

• static value_type mapping(const operator_type& f, const value_type& x) Applies operator f to value x.

The concept checks that these expressions are valid and return the exact stated types. It does not require any operation to be constexpr. Associativity, identity laws, and the interaction between mapping and op must be satisfied by the implementation.

Built-in acted monoids also expose two metadata flags:

• static constexpr bool commutative describes the value operation op.
• static constexpr bool operator_commutative describes the operator operation op_comp.

Generic data structures may use these flags to select faster representations or algorithms. Both members are deliberately optional and are not part of IsActedMonoid, so a contest-local acted monoid may omit them. An omitted flag is treated conservatively by data structures that inspect it.

Commutative Acted Group

m1une::acted_monoid::IsCommutativeActedGroup extends IsActedMonoid with an inverse for the value monoid:

• static value_type inv(const value_type& x) Returns the inverse of x with respect to the value operation op.

The concept checks only the interface. The value operation should satisfy the commutative group laws, and mapping should still distribute over op.

Complexity

These concepts are compile-time interface checks and have no runtime cost.

Required by

• Beats Acted Monoid Concept (beats_acted_monoid/concept.hpp)
• Dynamic Lazy Monoid Array (ds/dynamic_array/dynamic_lazy_monoid_array.hpp)
• Persistent Dynamic Lazy Monoid Array (ds/dynamic_array/persistent_dynamic_lazy_monoid_array.hpp)
• Rollback Dynamic Lazy Monoid Array (ds/dynamic_array/rollback_dynamic_lazy_monoid_array.hpp)
• Lazy Link-Cut Tree (ds/dynamic_tree/lazy_link_cut_tree.hpp)
• Lazy Path Link-Cut Tree (ds/dynamic_tree/lazy_path_link_cut_tree.hpp)
• Dynamic Lazy Segment Tree (ds/segtree/dynamic_lazy_segtree.hpp)
• Lazy Segment Tree (ds/segtree/lazy_segtree.hpp)
• Persistent Dynamic Lazy Segment Tree (ds/segtree/persistent_dynamic_lazy_segtree.hpp)
• Persistent Lazy Segment Tree (ds/segtree/persistent_lazy_segtree.hpp)
• ds/segtree/persistent_segtree_beats.hpp
• Rollback Dynamic Lazy Segment Tree (ds/segtree/rollback_dynamic_lazy_segtree.hpp)
• Rollback Lazy Segment Tree (ds/segtree/rollback_lazy_segtree.hpp)
• Rollback Segment Tree Beats (ds/segtree/rollback_segtree_beats.hpp)
• Generic Segment Tree Beats! (ds/segtree/segtree_beats.hpp)

Verified with

• verify/acted_monoid/range_bitwise_and_or_xor_range_sum.test.cpp
• verify/acted_monoid/range_bitwise_and_or_xor_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/ds/dynamic_array/dynamic_lazy_monoid_array.test.cpp
• verify/ds/dynamic_array/dynamic_lazy_monoid_array_range_ap.test.cpp
• verify/ds/dynamic_array/persistent_dynamic_lazy_monoid_array.test.cpp
• verify/ds/dynamic_array/persistent_dynamic_lazy_monoid_array_range_ap.test.cpp
• verify/ds/dynamic_tree/lazy_link_cut_tree.test.cpp
• verify/ds/dynamic_tree/lazy_path_link_cut_tree.test.cpp
• verify/ds/persistent_cow.test.cpp
• verify/ds/persistent_cow.test.cpp
• verify/ds/persistent_cow.test.cpp
• verify/ds/persistent_release.test.cpp
• verify/ds/rollback_counterparts.test.cpp
• verify/ds/rollback_counterparts.test.cpp
• verify/ds/rollback_counterparts.test.cpp
• verify/ds/segtree/dynamic_lazy_segtree.test.cpp
• verify/ds/segtree/lazy_segtree.test.cpp
• verify/ds/segtree/persistent_dynamic_lazy_segtree.test.cpp
• verify/ds/segtree/persistent_lazy_segtree.test.cpp
• verify/ds/segtree/persistent_segtree_beats.test.cpp
• verify/ds/segtree/range_add_range_min.test.cpp
• verify/ds/segtree/range_update_range_product.test.cpp
• verify/ds/segtree/range_update_range_product.test.cpp
• verify/ds/segtree/segtree_beats.test.cpp
• verify/monoid/commutative_flags.test.cpp
• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_CONCEPT_HPP
#define M1UNE_ACTED_MONOID_CONCEPT_HPP 1

#include <concepts>

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

#endif  // M1UNE_ACTED_MONOID_CONCEPT_HPP

#line 1 "acted_monoid/concept.hpp"



#include <concepts>

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

Back to top page