Monoid
(monoid/monoid.hpp)

• View this file on GitHub
• Last update: 2025-10-01 15:41:05+09:00
• Include: #include "monoid/monoid.hpp"
• Link: View error logs on GitHub Actions

Overview

This file provides a generic struct to define a Monoid, which is a fundamental algebraic structure used in various data structures.

Properties

A monoid is a set of elements $S$ equipped with a single binary operation $(\cdot)$ that satisfies the following two properties:

1. Associativity: For any three elements $a, b, c \in S$, the equation $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ holds.
2. Identity Element: There exists an identity element $e \in S$ such that for any element $a \in S$, the equation $e \cdot a = a \cdot e = a$ holds.

This monoid struct serves as a template for creating specific monoids (like for addition, multiplication, etc.) that can be passed as template parameters to data structures like the Segment Tree.

Template Parameters

• typename T The type of the elements in the monoid’s set (e.g., int, long long, std::pair<mint, mint>).

• auto operation A lambda or function pointer representing the binary operation $(\cdot)$ of the monoid. It must take two arguments of type T and return a T.

• auto identity A lambda or function pointer that returns the identity element $e$ of the monoid.

• bool commutative A boolean flag indicating whether the binary operation is commutative (i.e., if $a \cdot b = b \cdot a$). This is an optional optimization hint for some data structures.

Members

• using value_type = T; An alias for the element type T.

• static constexpr auto op = operation; The binary operation function.

• static constexpr auto id = identity; The identity element function.

• static constexpr bool is_commutative = commutative; The commutativity flag.

Usage Example

The library provides several pre-defined monoids. Here is how add_monoid is defined using this base struct:

template <typename T>
using add_monoid = monoid<T, [](T a, T b) { return a + b; }, []() { return T(0); }, true>;

This defines a monoid for addition on any type T, where the operation is +, the identity is 0, and the operation is commutative.

Required by

• Lazy Segment Tree (data_structure/segtree/lazy_segtree.hpp)
• Segment Tree (data_structure/segtree/segtree.hpp)
• Acted Monoid (monoid/acted_monoid.hpp)
• monoid/acted_monoids/range_add_range_max.hpp
• monoid/acted_monoids/range_add_range_max.hpp
• monoid/acted_monoids/range_add_range_min.hpp
• monoid/acted_monoids/range_add_range_min.hpp
• monoid/acted_monoids/range_add_range_sum.hpp
• monoid/acted_monoids/range_add_range_sum.hpp
• monoid/acted_monoids/range_affine_range_minmax.hpp
• monoid/acted_monoids/range_affine_range_minmax.hpp
• monoid/acted_monoids/range_affine_range_sum.hpp
• monoid/acted_monoids/range_affine_range_sum.hpp
• monoid/acted_monoids/range_update_range_max.hpp
• monoid/acted_monoids/range_update_range_max.hpp
• monoid/acted_monoids/range_update_range_min.hpp
• monoid/acted_monoids/range_update_range_min.hpp
• monoid/acted_monoids/range_update_range_sum.hpp
• monoid/acted_monoids/range_update_range_sum.hpp
• monoid/monoid_addsz.hpp
• monoid/monoids/add_monoid.hpp
• monoid/monoids/affine_monoid.hpp
• monoid/monoids/and_monoid.hpp
• monoid/monoids/max_monoid.hpp
• monoid/monoids/min_monoid.hpp
• monoid/monoids/minmax_monoid.hpp
• monoid/monoids/mul_monoid.hpp
• monoid/monoids/or_monoid.hpp
• monoid/monoids/update_monoid.hpp
• monoid/monoids/xor_monoid.hpp
• monoid/prim_acted_monoids.hpp
• monoid/prim_acted_monoids.hpp
• monoid/prim_acted_monoids.hpp
• monoid/prim_monoids.hpp
• monoid/prim_monoids.hpp

Verified with

• verify/unit_test/lazy_segtree.test.cpp
• verify/unit_test/lazy_segtree.test.cpp
• verify/unit_test/lazy_segtree.test.cpp
• verify/unit_test/segtree.test.cpp
• verify/unit_test/segtree.test.cpp

Code

#ifndef M1UNE_MONOID_HPP
#define M1UNE_MONOID_HPP 1

#include <concepts>
#include <functional>
#include <type_traits>

namespace m1une {

template <typename T, auto operation, auto identity, bool commutative>
struct monoid {
    static_assert(std::is_invocable_r_v<T, decltype(operation), T, T>, "operation must work as T(T, T)");
    static_assert(std::is_invocable_r_v<T, decltype(identity)>, "identity must work as T()");

    using value_type = T;
    static constexpr auto op = operation;
    static constexpr auto id = identity;
    static constexpr bool is_commutative = commutative;
};

template <typename T>
concept Monoid = requires(typename T::value_type v) {
    typename T::value_type;
    { T::op(v, v) } -> std::same_as<typename T::value_type>;
    { T::id() } -> std::same_as<typename T::value_type>;
    { T::is_commutative } -> std::convertible_to<bool>;
};

}  // namespace m1une

#endif  // M1UNE_MONOID_HPP

#line 1 "monoid/monoid.hpp"



#include <concepts>
#include <functional>
#include <type_traits>

namespace m1une {

template <typename T, auto operation, auto identity, bool commutative>
struct monoid {
    static_assert(std::is_invocable_r_v<T, decltype(operation), T, T>, "operation must work as T(T, T)");
    static_assert(std::is_invocable_r_v<T, decltype(identity)>, "identity must work as T()");

    using value_type = T;
    static constexpr auto op = operation;
    static constexpr auto id = identity;
    static constexpr bool is_commutative = commutative;
};

template <typename T>
concept Monoid = requires(typename T::value_type v) {
    typename T::value_type;
    { T::op(v, v) } -> std::same_as<typename T::value_type>;
    { T::id() } -> std::same_as<typename T::value_type>;
    { T::is_commutative } -> std::convertible_to<bool>;
};

}  // namespace m1une

Back to top page