algebraic-structure/magma.hpp

• View this file on GitHub
• Last update: 2026-06-28 15:32:36+09:00
• Include: #include "algebraic-structure/magma.hpp"

Depends on

• algebraic-structure/util.hpp

Required by

• algebraic-structure/group.hpp
• algebraic-structure/monoid-action.hpp
• algebraic-structure/monoid.hpp
• data-structure/sparse-table.hpp
• data-structure/wavelet-matrix-with-segment-tree.hpp
• モノイド版 Floor Sum (math/floor-monoid-product.hpp)
• 多項式版 floor sum (math/polynomial-floor-sum.hpp)
• Dual Segment Tree (segment-tree/dual-segment-tree.hpp)
• よく使う Lazy Segment Tree (segment-tree/lazy-segment-tree-util.hpp)
• Lazy Segment Tree (segment-tree/lazy-segment-tree.hpp)
• Persistent Segment Tree (segment-tree/persistent-segment-tree.hpp)
• よく使う Segment Tree (segment-tree/segment-tree-util.hpp)
• Segment Tree (segment-tree/segment-tree.hpp)
• 木上の距離 (tree/distance.hpp)
• LCA ベースの Auxiliary Tree (tree/lca-auxiliary-tree.hpp)
• Lowest Common Ancestor (tree/lowest-common-ancestor.hpp)
• Persistent Potentialized Union Find (union-find/persistent-potentialized-union-find.hpp)
• ポテンシャル付き Union Find (union-find/potentialized-union-find.hpp)

Verified with

• verify/data-structure/LC_point_add_rectangle_sum.wavelet_matrix.test.cpp
• verify/data-structure/LC_staticrmq.test.cpp
• verify/math/LC_sum_of_floor_of_linear.monoid.test.cpp
• verify/segment-tree/LC_point_add_range_sum.test.cpp
• verify/segment-tree/LC_point_set_range_composite.test.cpp
• verify/segment-tree/LC_range_affine_point_get.test.cpp
• verify/segment-tree/LC_range_affine_range_sum.test.cpp
• verify/tree/LC_lowest_common_ancestor.test.cpp
• verify/union-find/LC_unionfind_with_potential.test.cpp

Code

#pragma once
#include "algebraic-structure/util.hpp"

#ifdef __cpp_concepts
template <class M>
concept Magma = requires(typename M::value_type x, typename M::value_type y) {
  typename M::value_type;
  { M::op(x, y) } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMagma {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
};
template <class T>
struct MulMagma {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
};
template <class T, T id>
struct MaxMagma {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
};
template <class T, T id>
struct MinMagma {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
};

#line 2 "algebraic-structure/util.hpp"
#ifdef __cpp_concepts
#define REQUIRES(...) requires __VA_ARGS__
#else
#define REQUIRES(...)
#endif
#line 3 "algebraic-structure/magma.hpp"

#ifdef __cpp_concepts
template <class M>
concept Magma = requires(typename M::value_type x, typename M::value_type y) {
  typename M::value_type;
  { M::op(x, y) } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMagma {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
};
template <class T>
struct MulMagma {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
};
template <class T, T id>
struct MaxMagma {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
};
template <class T, T id>
struct MinMagma {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
};

Back to top page