Segment Tree (monoid wrapper)
(datastructure/segtree.hpp)

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

概要

• atcoder::segtree を monoid 構造体 1 つで指定するためのエイリアス。

使い方

• segtree<M>: M は S, op, e を static メンバとして持つ構造体。algebra/ 以下のものか、同じ形で自作したもの。
• 以降は atcoder::segtree と同じ。

Depends on

• Algebra: Concept (algebra/concept.hpp)

Required by

• Manhattan MST (graph/manhattan_mst.hpp)

Verified with

• test/aoj/DSL_2_A.test.cpp
• test/library-checker/manhattanmst.test.cpp
• test/library-checker/point_set_range_composite.test.cpp
• test/unit/monoid.test.cpp

Code

#pragma once
#include <atcoder/segtree>

#include "algebra/concept.hpp"
template <monoid M>
using segtree = atcoder::segtree<typename M::S, M::op, M::e>;

#line 2 "datastructure/segtree.hpp"
#include <atcoder/segtree>

#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>;
};
#line 5 "datastructure/segtree.hpp"
template <monoid M>
using segtree = atcoder::segtree<typename M::S, M::op, M::e>;

Back to top page