Algebraic Structure（代数的構造）
(algorithm/Math/Algebra/algebra.hpp)

• View this file on GitHub
• Last update: 2025-07-06 12:46:03+09:00
• Include: #include "algorithm/Math/Algebra/algebra.hpp"

概要

「代数的構造 (algebraic structure) 」を定義するクラス群．

「半群 (semigroup)」や「モノイド (monoid)」，「群 (group)」といった代数的構造の性質は包含関係をもち，クラスの継承を用いて表すことができる．

参考

1. “代数的構造”. Wikipedia. https://ja.wikipedia.org/wiki/代数的構造.
2. “代数的構造の関係を図示してみた（マグマ、半群、モノイド、群、アーベル群、環、可換環、整域、体）”. 毛糸ブログ. https://keito.luxe/2020/01/25/algebra/.
3. 松本眞. “代数系への入門 モノイド・群・環”. https://www.math.sci.hiroshima-u.ac.jp/m-mat/TEACH/daisu-nyumon202108.pdf.
4. iTHEMS. “Computers as a Playground for Mathematics - Coffee Meeting Talk by Taketo Sano (iTHEMS)”. YouTube. https://www.youtube.com/live/qiqJ0jahqG4?si=OKWvluYqKdBfL_Ua.
5. taketo1024. X (Twitter). https://x.com/taketo1024/status/1915929616566587599.

Required by

• Binary Indexed Tree (algorithm/DataStructure/SegmentTree/binary_indexed_tree.hpp)
• 二次元Binary Indexed Tree (algorithm/DataStructure/SegmentTree/binary_indexed_tree_2d.hpp)
• Dynamic Segment Tree（動的セグメント木） (algorithm/DataStructure/SegmentTree/dynamic_segment_tree.hpp)
• Lazy Segment Tree（遅延評価セグメント木） (algorithm/DataStructure/SegmentTree/lazy_segment_tree.hpp)
• Segment Tree (algorithm/DataStructure/SegmentTree/segment_tree.hpp)
• Sparse Table (algorithm/DataStructure/SegmentTree/sparse_table.hpp)

Verified with

• verify/aoj-2842-binary_indexed_tree_2d.test.cpp
• verify/aoj-DSL_2_A-dynamic_segment_tree.test.cpp
• verify/aoj-DSL_2_A-segment_tree.test.cpp
• verify/aoj-DSL_2_B-binary_indexed_tree.test.cpp
• verify/aoj-DSL_2_B-dynamic_segment_tree.test.cpp
• verify/aoj-DSL_2_B-segment_tree.test.cpp
• verify/aoj-DSL_2_F-lazy_segment_tree.test.cpp
• verify/aoj-DSL_2_G-lazy_segment_tree.test.cpp
• verify/aoj-DSL_2_H-lazy_segment_tree.test.cpp
• verify/aoj-DSL_2_I-lazy_segment_tree.test.cpp
• verify/yosupo-point_add_range_sum-binary_indexed_tree.test.cpp
• verify/yosupo-point_add_range_sum-segment_tree.test.cpp
• verify/yosupo-point_set_range_composite-segment_tree.test.cpp
• verify/yosupo-range_affine_range_sum-lazy_segment_tree.test.cpp
• verify/yosupo-staticrmp-sparse_table.test.cpp
• verify/yosupo-vertex_add_path_sum-heavy_light_decomposition.test.cpp
• verify/yosupo-vertex_add_subtree_sum-heavy_light_decomposition.test.cpp

Code

#ifndef ALGORITHM_ALGEBRA_HPP
#define ALGORITHM_ALGEBRA_HPP

#include <algorithm>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>
#include <utility>

namespace algorithm {

namespace algebra {

template <typename S>
class Set {
public:
    using value_type = S;

protected:
    value_type val;

public:
    constexpr Set() : val() {}
    constexpr Set(const value_type &val) : val(val) {}
    constexpr Set(value_type &&val) : val(std::move(val)) {}

    friend constexpr bool operator==(const Set &lhs, const Set &rhs) { return lhs.value() == rhs.value(); }
    friend std::istream &operator>>(std::istream &is, Set &rhs) { return is >> rhs.val; }
    friend std::ostream &operator<<(std::ostream &os, const Set &rhs) { return os << rhs.value(); }

    constexpr value_type value() const { return val; }
};

template <typename S, auto op>
class Semigroup : public Set<S> {
    static_assert(std::is_invocable_r<S, decltype(op), S, S>::value);

public:
    using base_type = Set<S>;
    using value_type = typename base_type::value_type;

    constexpr Semigroup() : base_type() {}
    constexpr Semigroup(const value_type &val) : base_type(val) {}
    constexpr Semigroup(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Semigroup operator*(const Semigroup &lhs, const Semigroup &rhs) { return Semigroup(op(lhs.value(), rhs.value())); }

    static constexpr auto get_op() { return op; }
};

template <typename S, auto op, auto e>
class Monoid : public Semigroup<S, op> {
    static_assert(std::is_invocable_r<S, decltype(e)>::value);

public:
    using base_type = Semigroup<S, op>;
    using value_type = typename base_type::value_type;

    constexpr Monoid() : base_type() {}
    constexpr Monoid(const value_type &val) : base_type(val) {}
    constexpr Monoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Monoid operator*(const Monoid &lhs, const Monoid &rhs) { return Monoid(op(lhs.value(), rhs.value())); }

    static constexpr auto get_e() { return e; }
    static constexpr Monoid one() { return Monoid(e()); }  // return identity element.
};

template <typename S, auto op, auto e, auto inverse>
class Group : public Monoid<S, op, e> {
    static_assert(std::is_invocable_r<S, decltype(inverse), S>::value);

public:
    using base_type = Monoid<S, op, e>;
    using value_type = typename base_type::value_type;

    constexpr Group() : base_type() {}
    constexpr Group(const value_type &val) : base_type(val) {}
    constexpr Group(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Group operator*(const Group &lhs, const Group &rhs) { return Group(op(lhs.value(), rhs.value())); }

    static constexpr auto get_inverse() { return inverse; }
    static constexpr Group one() { return Group(e()); }                    // return identity element.
    constexpr Group inv() const { return Group(inverse(this->value())); }  // return inverse element.
};

template <typename F, auto compose, auto id, typename X, auto mapping>
class OperatorMonoid : public Monoid<F, compose, id> {
    static_assert(std::is_invocable_r<X, decltype(mapping), F, X>::value);

public:
    using base_type = Monoid<F, compose, id>;
    using value_type = typename base_type::value_type;
    using acted_type = X;

    constexpr OperatorMonoid() : base_type() {}
    constexpr OperatorMonoid(const value_type &val) : base_type(val) {}
    constexpr OperatorMonoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr OperatorMonoid operator*(const OperatorMonoid &lhs, const OperatorMonoid &rhs) { return OperatorMonoid(compose(lhs.value(), rhs.value())); }

    static constexpr auto get_mapping() { return mapping; }
    static constexpr OperatorMonoid one() { return OperatorMonoid(id()); }  // return identity mapping.
    constexpr acted_type act(const acted_type &x) const { return mapping(this->value(), x); }
    template <class S>
    constexpr S act(const S &x) const {
        static_assert(std::is_base_of<Set<acted_type>, S>::value);
        return S(mapping(this->value(), x.value()));
    }
};

namespace element {

template <typename S>
constexpr auto zero = []() -> S { return S(); };

template <typename S>
constexpr auto one = []() -> S { return 1; };

template <typename S>
constexpr auto min = []() -> S { return std::numeric_limits<S>::min(); };

template <typename S>
constexpr auto max = []() -> S { return std::numeric_limits<S>::max(); };

template <typename S>
constexpr auto one_below_max = []() -> S { return std::numeric_limits<S>::max() - 1; };

template <typename S>
constexpr auto lowest = []() -> S { return std::numeric_limits<S>::lowest(); };

template <typename S>
constexpr auto one_above_lowest = []() -> S { return std::numeric_limits<S>::lowest() + 1; };

}  // namespace element

namespace unary_operator {

template <typename S>
constexpr auto identity = [](const S &val) -> S { return val; };

template <typename S>
constexpr auto negate = [](const S &val) -> S { return -val; };

}  // namespace unary_operator

namespace binary_operator {

template <typename T, typename S = T>
constexpr auto plus = [](const T &lhs, const S &rhs) -> S { return lhs + rhs; };

template <typename T, typename S = T>
constexpr auto mul = [](const T &lhs, const S &rhs) -> S { return lhs * rhs; };

template <typename T, typename S = T>
constexpr auto bit_and = [](const T &lhs, const S &rhs) -> S { return lhs & rhs; };

template <typename T, typename S = T>
constexpr auto bit_or = [](const T &lhs, const S &rhs) -> S { return lhs | rhs; };

template <typename T, typename S = T>
constexpr auto bit_xor = [](const T &lhs, const S &rhs) -> S { return lhs ^ rhs; };

template <typename T, typename S = T>
constexpr auto min = [](const T &lhs, const S &rhs) -> S { return std::min<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto max = [](const T &lhs, const S &rhs) -> S { return std::max<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto gcd = [](const T &lhs, const S &rhs) -> S { return std::gcd(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto lcm = [](const T &lhs, const S &rhs) -> S { return std::lcm(lhs, rhs); };

template <typename F, auto id, typename X = F>
constexpr auto assign_if_not_id = [](const F &lhs, const X &rhs) -> X {
    static_assert(std::is_invocable_r<F, decltype(id)>::value);
    return (lhs == id() ? rhs : lhs);
};

}  // namespace binary_operator

namespace monoid {

template <typename S>
using minimum = Monoid<S, binary_operator::min<S>, element::max<S>>;

template <typename S>
using minimum_safe = Monoid<S, binary_operator::min<S>, element::one_below_max<S>>;

template <typename S>
using maximum = Monoid<S, binary_operator::max<S>, element::lowest<S>>;

template <typename S>
using maximum_safe = Monoid<S, binary_operator::max<S>, element::one_above_lowest<S>>;

template <typename S>
using addition = Monoid<S, binary_operator::plus<S>, element::zero<S>>;

template <typename S>
using multiplication = Monoid<S, binary_operator::mul<S>, element::one<S>>;

template <typename S>
using bit_xor = Monoid<S, binary_operator::bit_xor<S>, element::zero<S>>;

}  // namespace monoid

namespace group {

template <typename S>
using addition = Group<S, binary_operator::plus<S>, element::zero<S>, unary_operator::negate<S>>;

template <typename S>
using bit_xor = Group<S, binary_operator::bit_xor<S>, element::zero<S>, unary_operator::identity<S>>;

}  // namespace group

namespace operator_monoid {

template <typename F, typename X = F>
using assign_for_minimum = OperatorMonoid<
    F, binary_operator::assign_if_not_id<F, element::max<F>>, element::max<F>,
    X, binary_operator::assign_if_not_id<F, element::max<F>, X>>;

template <typename F, typename X = F>
using assign_for_maximum = OperatorMonoid<
    F, binary_operator::assign_if_not_id<F, element::lowest<F>>, element::lowest<F>,
    X, binary_operator::assign_if_not_id<F, element::lowest<F>, X>>;

template <typename F, typename X = F>
using addition = OperatorMonoid<
    F, binary_operator::plus<F>, element::zero<F>,
    X, binary_operator::plus<F, X>>;

}  // namespace operator_monoid

}  // namespace algebra

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/Algebra/algebra.hpp"



#include <algorithm>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>
#include <utility>

namespace algorithm {

namespace algebra {

template <typename S>
class Set {
public:
    using value_type = S;

protected:
    value_type val;

public:
    constexpr Set() : val() {}
    constexpr Set(const value_type &val) : val(val) {}
    constexpr Set(value_type &&val) : val(std::move(val)) {}

    friend constexpr bool operator==(const Set &lhs, const Set &rhs) { return lhs.value() == rhs.value(); }
    friend std::istream &operator>>(std::istream &is, Set &rhs) { return is >> rhs.val; }
    friend std::ostream &operator<<(std::ostream &os, const Set &rhs) { return os << rhs.value(); }

    constexpr value_type value() const { return val; }
};

template <typename S, auto op>
class Semigroup : public Set<S> {
    static_assert(std::is_invocable_r<S, decltype(op), S, S>::value);

public:
    using base_type = Set<S>;
    using value_type = typename base_type::value_type;

    constexpr Semigroup() : base_type() {}
    constexpr Semigroup(const value_type &val) : base_type(val) {}
    constexpr Semigroup(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Semigroup operator*(const Semigroup &lhs, const Semigroup &rhs) { return Semigroup(op(lhs.value(), rhs.value())); }

    static constexpr auto get_op() { return op; }
};

template <typename S, auto op, auto e>
class Monoid : public Semigroup<S, op> {
    static_assert(std::is_invocable_r<S, decltype(e)>::value);

public:
    using base_type = Semigroup<S, op>;
    using value_type = typename base_type::value_type;

    constexpr Monoid() : base_type() {}
    constexpr Monoid(const value_type &val) : base_type(val) {}
    constexpr Monoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Monoid operator*(const Monoid &lhs, const Monoid &rhs) { return Monoid(op(lhs.value(), rhs.value())); }

    static constexpr auto get_e() { return e; }
    static constexpr Monoid one() { return Monoid(e()); }  // return identity element.
};

template <typename S, auto op, auto e, auto inverse>
class Group : public Monoid<S, op, e> {
    static_assert(std::is_invocable_r<S, decltype(inverse), S>::value);

public:
    using base_type = Monoid<S, op, e>;
    using value_type = typename base_type::value_type;

    constexpr Group() : base_type() {}
    constexpr Group(const value_type &val) : base_type(val) {}
    constexpr Group(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Group operator*(const Group &lhs, const Group &rhs) { return Group(op(lhs.value(), rhs.value())); }

    static constexpr auto get_inverse() { return inverse; }
    static constexpr Group one() { return Group(e()); }                    // return identity element.
    constexpr Group inv() const { return Group(inverse(this->value())); }  // return inverse element.
};

template <typename F, auto compose, auto id, typename X, auto mapping>
class OperatorMonoid : public Monoid<F, compose, id> {
    static_assert(std::is_invocable_r<X, decltype(mapping), F, X>::value);

public:
    using base_type = Monoid<F, compose, id>;
    using value_type = typename base_type::value_type;
    using acted_type = X;

    constexpr OperatorMonoid() : base_type() {}
    constexpr OperatorMonoid(const value_type &val) : base_type(val) {}
    constexpr OperatorMonoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr OperatorMonoid operator*(const OperatorMonoid &lhs, const OperatorMonoid &rhs) { return OperatorMonoid(compose(lhs.value(), rhs.value())); }

    static constexpr auto get_mapping() { return mapping; }
    static constexpr OperatorMonoid one() { return OperatorMonoid(id()); }  // return identity mapping.
    constexpr acted_type act(const acted_type &x) const { return mapping(this->value(), x); }
    template <class S>
    constexpr S act(const S &x) const {
        static_assert(std::is_base_of<Set<acted_type>, S>::value);
        return S(mapping(this->value(), x.value()));
    }
};

namespace element {

template <typename S>
constexpr auto zero = []() -> S { return S(); };

template <typename S>
constexpr auto one = []() -> S { return 1; };

template <typename S>
constexpr auto min = []() -> S { return std::numeric_limits<S>::min(); };

template <typename S>
constexpr auto max = []() -> S { return std::numeric_limits<S>::max(); };

template <typename S>
constexpr auto one_below_max = []() -> S { return std::numeric_limits<S>::max() - 1; };

template <typename S>
constexpr auto lowest = []() -> S { return std::numeric_limits<S>::lowest(); };

template <typename S>
constexpr auto one_above_lowest = []() -> S { return std::numeric_limits<S>::lowest() + 1; };

}  // namespace element

namespace unary_operator {

template <typename S>
constexpr auto identity = [](const S &val) -> S { return val; };

template <typename S>
constexpr auto negate = [](const S &val) -> S { return -val; };

}  // namespace unary_operator

namespace binary_operator {

template <typename T, typename S = T>
constexpr auto plus = [](const T &lhs, const S &rhs) -> S { return lhs + rhs; };

template <typename T, typename S = T>
constexpr auto mul = [](const T &lhs, const S &rhs) -> S { return lhs * rhs; };

template <typename T, typename S = T>
constexpr auto bit_and = [](const T &lhs, const S &rhs) -> S { return lhs & rhs; };

template <typename T, typename S = T>
constexpr auto bit_or = [](const T &lhs, const S &rhs) -> S { return lhs | rhs; };

template <typename T, typename S = T>
constexpr auto bit_xor = [](const T &lhs, const S &rhs) -> S { return lhs ^ rhs; };

template <typename T, typename S = T>
constexpr auto min = [](const T &lhs, const S &rhs) -> S { return std::min<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto max = [](const T &lhs, const S &rhs) -> S { return std::max<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto gcd = [](const T &lhs, const S &rhs) -> S { return std::gcd(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto lcm = [](const T &lhs, const S &rhs) -> S { return std::lcm(lhs, rhs); };

template <typename F, auto id, typename X = F>
constexpr auto assign_if_not_id = [](const F &lhs, const X &rhs) -> X {
    static_assert(std::is_invocable_r<F, decltype(id)>::value);
    return (lhs == id() ? rhs : lhs);
};

}  // namespace binary_operator

namespace monoid {

template <typename S>
using minimum = Monoid<S, binary_operator::min<S>, element::max<S>>;

template <typename S>
using minimum_safe = Monoid<S, binary_operator::min<S>, element::one_below_max<S>>;

template <typename S>
using maximum = Monoid<S, binary_operator::max<S>, element::lowest<S>>;

template <typename S>
using maximum_safe = Monoid<S, binary_operator::max<S>, element::one_above_lowest<S>>;

template <typename S>
using addition = Monoid<S, binary_operator::plus<S>, element::zero<S>>;

template <typename S>
using multiplication = Monoid<S, binary_operator::mul<S>, element::one<S>>;

template <typename S>
using bit_xor = Monoid<S, binary_operator::bit_xor<S>, element::zero<S>>;

}  // namespace monoid

namespace group {

template <typename S>
using addition = Group<S, binary_operator::plus<S>, element::zero<S>, unary_operator::negate<S>>;

template <typename S>
using bit_xor = Group<S, binary_operator::bit_xor<S>, element::zero<S>, unary_operator::identity<S>>;

}  // namespace group

namespace operator_monoid {

template <typename F, typename X = F>
using assign_for_minimum = OperatorMonoid<
    F, binary_operator::assign_if_not_id<F, element::max<F>>, element::max<F>,
    X, binary_operator::assign_if_not_id<F, element::max<F>, X>>;

template <typename F, typename X = F>
using assign_for_maximum = OperatorMonoid<
    F, binary_operator::assign_if_not_id<F, element::lowest<F>>, element::lowest<F>,
    X, binary_operator::assign_if_not_id<F, element::lowest<F>, X>>;

template <typename F, typename X = F>
using addition = OperatorMonoid<
    F, binary_operator::plus<F>, element::zero<F>,
    X, binary_operator::plus<F, X>>;

}  // namespace operator_monoid

}  // namespace algebra

}  // namespace algorithm

Back to top page