Algebra: Concept
(algebra/concept.hpp)

• View this file on GitHub
• Last update: 2026-10-26 01:30:50+09:00
• Include: #include "algebra/concept.hpp"

概要

• segtree, lazy_segtree, dual_segtree, sparse_table, semiring_matrix, weighted_dsu に渡す構造体の要件。

使い方

• semigroup<M>: M::S と M::op(S, S) -> S を持つ。
• monoid<M>: semigroup<M> に加えて M::e() -> S を持つ。
• group<G>: monoid<G> に加えて G::inv(S) -> S を持つ。
• action<A>: A::F, A::composition(F, F) -> F, A::id() -> F, bool A::composition_commutative を持つ。
• acted_monoid<A>: monoid<A> と action<A> に加えて A::mapping(F, S) -> S を持つ。
• semiring<R>: R::S, R::add(S, S) -> S, R::zero() -> S, R::mul(S, S) -> S, R::one() -> S を持つ。

Required by

• Dual Segment Tree (datastructure/dual_segtree.hpp)
• Lazy Segment Tree (acted monoid wrapper) (datastructure/lazy_segtree.hpp)
• Plus Minus One RMQ (datastructure/plus_minus_one_rmq.hpp)
• Segment Tree (monoid wrapper) (datastructure/segtree.hpp)
• Sparse Table (datastructure/sparse_table.hpp)
• Sqrt Tree (datastructure/sqrt_tree.hpp)
• Weighted DSU (datastructure/weighted_dsu.hpp)
• 最小共通祖先(LCA) (graph/lowest_common_ancestor.hpp)
• Manhattan MST (graph/manhattan_mst.hpp)
• Matrix (math/matrix.hpp)
• Range Update Range Hash (string/range_update_range_hash.hpp)

Verified with

• test/aoj/0355.test.cpp
• test/aoj/DSL_2_A.test.cpp
• test/aoj/DSL_2_G.test.cpp
• test/library-checker/lca.test.cpp
• test/library-checker/manhattanmst.test.cpp
• test/library-checker/matrix_product.test.cpp
• test/library-checker/point_set_range_composite.test.cpp
• test/library-checker/pow_of_matrix.test.cpp
• test/library-checker/range_affine_point_get.test.cpp
• test/library-checker/staticrmq.test.cpp
• test/library-checker/staticrmq_sqrt_tree.test.cpp
• test/library-checker/unionfind_with_potential.test.cpp
• test/library-checker/unionfind_with_potential_non_commutative_group.test.cpp
• test/unit/dual_segtree.test.cpp
• test/unit/matrix.test.cpp
• test/unit/monoid.test.cpp
• test/unit/sparse_table.test.cpp
• test/unit/sqrt_tree.test.cpp
• test/unit/string_hash.test.cpp
• test/unit/weighted_dsu.test.cpp

Code

#pragma once
#include <concepts>
template <class M>
concept semigroup = requires(typename M::S a, typename M::S b) {
    { M::op(a, b) } -> std::same_as<typename M::S>;
};
template <class M>
concept monoid = semigroup<M> && requires {
    { M::e() } -> std::same_as<typename M::S>;
};
template <class G>
concept group = monoid<G> && requires(typename G::S a) {
    { G::inv(a) } -> std::same_as<typename G::S>;
};
template <class A>
concept action = requires(typename A::F f, typename A::F g) {
    { A::composition(f, g) } -> std::same_as<typename A::F>;
    { A::id() } -> std::same_as<typename A::F>;
    { A::composition_commutative } -> std::convertible_to<bool>;
};
template <class A>
concept acted_monoid = monoid<A> && action<A> && requires(typename A::S x, typename A::F f) {
    { A::mapping(f, x) } -> std::same_as<typename A::S>;
};
template <class R>
concept semiring = requires(typename R::S a, typename R::S b) {
    { R::add(a, b) } -> std::same_as<typename R::S>;
    { R::zero() } -> std::same_as<typename R::S>;
    { R::mul(a, b) } -> std::same_as<typename R::S>;
    { R::one() } -> std::same_as<typename R::S>;
};

#line 2 "algebra/concept.hpp"
#include <concepts>
template <class M>
concept semigroup = requires(typename M::S a, typename M::S b) {
    { M::op(a, b) } -> std::same_as<typename M::S>;
};
template <class M>
concept monoid = semigroup<M> && requires {
    { M::e() } -> std::same_as<typename M::S>;
};
template <class G>
concept group = monoid<G> && requires(typename G::S a) {
    { G::inv(a) } -> std::same_as<typename G::S>;
};
template <class A>
concept action = requires(typename A::F f, typename A::F g) {
    { A::composition(f, g) } -> std::same_as<typename A::F>;
    { A::id() } -> std::same_as<typename A::F>;
    { A::composition_commutative } -> std::convertible_to<bool>;
};
template <class A>
concept acted_monoid = monoid<A> && action<A> && requires(typename A::S x, typename A::F f) {
    { A::mapping(f, x) } -> std::same_as<typename A::S>;
};
template <class R>
concept semiring = requires(typename R::S a, typename R::S b) {
    { R::add(a, b) } -> std::same_as<typename R::S>;
    { R::zero() } -> std::same_as<typename R::S>;
    { R::mul(a, b) } -> std::same_as<typename R::S>;
    { R::one() } -> std::same_as<typename R::S>;
};

Back to top page