Src/DataStructure/SegmentTree/SegmentTreeConcept.hpp

• View this file on GitHub
• Last update: 2025-06-25 16:48:25+09:00
• Include: #include "Src/DataStructure/SegmentTree/SegmentTreeConcept.hpp"

Depends on

• Src/Algebra/Monoid/MonoidConcept.hpp
• Src/Algebra/Semigroup/SemigroupConcept.hpp

Required by

• Lazy Segment Tree (Src/DataStructure/SegmentTree/LazySegmentTree.hpp)
• Src/DataStructure/SegmentTree/SegmentTreeBeats.hpp
• Src/Utility/AreaOfUnionOfRectangles.hpp

Verified with

• Test/AtCoder/abc256_h.test.cpp
• ABC322-F Vacation Query (Test/AtCoder/abc322_f.test.cpp)
• Test/AtCoder/abc346_g.test.cpp
• Test/AtCoder/abc371_f.test.cpp
• Test/AtCoder/practice2_l.test.cpp
• Test/CF/CF895-E.test.cpp
• Test/LC/area_of_union_of_rectangles.test.cpp
• Test/LC/range_affine_range_sum.test.cpp

Code

#pragma once

#include "../../Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept MonoidWithAction = requires {
    requires Monoid<typename T::ValueMonoid>;
    requires Monoid<typename T::OperatorMonoid>;
    { T::mapping(
            std::declval<typename T::ValueMonoid::Element>(),
            std::declval<typename T::OperatorMonoid::Element>()
            ) } -> std::same_as<typename T::ValueMonoid::Element>; 
};

} // namespace concepts

} // namespace zawa

#line 2 "Src/DataStructure/SegmentTree/SegmentTreeConcept.hpp"

#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 4 "Src/DataStructure/SegmentTree/SegmentTreeConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept MonoidWithAction = requires {
    requires Monoid<typename T::ValueMonoid>;
    requires Monoid<typename T::OperatorMonoid>;
    { T::mapping(
            std::declval<typename T::ValueMonoid::Element>(),
            std::declval<typename T::OperatorMonoid::Element>()
            ) } -> std::same_as<typename T::ValueMonoid::Element>; 
};

} // namespace concepts

} // namespace zawa

Back to top page