Lazy Segment Tree (acted monoid wrapper)
(datastructure/lazy_segtree.hpp)

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

概要

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

使い方

• lazy_segtree<A>: A は S, op, e, F, mapping, composition, id を static メンバとして持つ構造体。algebra/ 以下のものか、同じ形で自作したもの。
• composition(f, g) は $f \circ g$（g が先）で ac-library と同じ。
• 以降は atcoder::lazy_segtree と同じ。

Depends on

• Algebra: Concept (algebra/concept.hpp)

Required by

• Range Update Range Hash (string/range_update_range_hash.hpp)

Verified with

• test/aoj/0355.test.cpp
• test/aoj/DSL_2_G.test.cpp
• test/unit/monoid.test.cpp
• test/unit/string_hash.test.cpp

Code

#pragma once
#include <atcoder/lazysegtree>

#include "algebra/concept.hpp"
template <acted_monoid A>
using lazy_segtree = atcoder::lazy_segtree<typename A::S, A::op, A::e, typename A::F, A::mapping, A::composition, A::id>;

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

#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/lazy_segtree.hpp"
template <acted_monoid A>
using lazy_segtree = atcoder::lazy_segtree<typename A::S, A::op, A::e, typename A::F, A::mapping, A::composition, A::id>;

Back to top page