lib/segtree/monoid.hpp

• View this file on GitHub
• Last update: 2026-03-15 03:14:58+09:00
• Include: #include "lib/segtree/monoid.hpp"

Required by

• 領域木 (lib/binary_tree/range_tree.hpp)
• Sliding Window Aggregation (lib/data_structure/swag.hpp)
• 永続双対セグメント木 (lib/persistent_ds/persistent_dual_segment_tree.hpp)
• 永続遅延評価セグメント木 (lib/persistent_ds/persistent_lazy_segment_tree.hpp)
• 永続セグメント木 (lib/persistent_ds/persistent_segment_tree.hpp)
• 双対セグメント木 (lib/segtree/dual_segment_tree.hpp)
• 動的遅延評価セグメント木 (lib/segtree/dynamic_lazy_segment_tree.hpp)
• 動的セグメント木 (lib/segtree/dynamic_segment_tree.hpp)
• 要素を特定のキー（条件）でフィルタリングして区間取得を行えるセグメント木 (lib/segtree/filtered_segment_tree.hpp)
• 遅延評価セグメント木 (lib/segtree/lazy_segment_tree.hpp)
• セグメント木 (lib/segtree/segment_tree.hpp)
• 二次元セグメント木 (lib/segtree/segment_tree_2d.hpp)
• lib/segtree/segment_tree_raq.hpp
• lib/tree/euler_tour_tree.hpp
• Link-Cut Tree (lib/tree/link_cut_tree.hpp)
• Segment Tree on Tree (lib/tree/segment_tree_on_tree.hpp)

Verified with

• test/aoj/challenge/1508.test.cpp
• test/aoj/challenge/2426.test.cpp
• test/aoj/challenge/2871.test.cpp
• test/aoj/course/ITP2_1_B.test.cpp
• test/aoj/dsl/dynamic_rmq.test.cpp
• test/aoj/dsl/raq_rmq.test.cpp
• test/aoj/dsl/rmq.2.test.cpp
• test/aoj/dsl/rmq.test.cpp
• test/aoj/dsl/rmq_ruq.test.cpp
• test/aoj/dsl/rsq_ruq.test.cpp
• test/aoj/dsl/ruq.test.cpp
• test/yosupo/data_structure/dynamic_tree_vertex_add_path_sum.test.cpp
• test/yosupo/data_structure/persistent_range_affine_range_sum.test.cpp
• test/yosupo/data_structure/point_add_rectangle_sum.2.test.cpp
• test/yosupo/data_structure/point_add_rectangle_sum.test.cpp
• test/yosupo/data_structure/point_set_range_composite.test.cpp
• test/yosupo/data_structure/point_set_range_composite_large_array.test.cpp
• test/yosupo/data_structure/point_set_range_frequency.test.cpp
• test/yosupo/data_structure/queue_operate_all_composite.test.cpp
• test/yosupo/data_structure/range_affine_range_sum.test.cpp
• test/yosupo/data_structure/range_affine_range_sum_large_array.test.cpp
• test/yosupo/data_structure/static_rmq.2.test.cpp
• test/yosupo/data_structure/static_rmq.3.test.cpp
• test/yosupo/data_structure/static_rmq.test.cpp
• test/yosupo/tree/vertex_add_subtree_sum.test.cpp
• test/yosupo/tree/vertex_set_path_composite.test.cpp
• test/yukicoder/0618.test.cpp
• test/yukicoder/0901.test.cpp
• test/yukicoder/1036.test.cpp
• test/yukicoder/1790.test.cpp
• test/yukicoder/3327.test.cpp

Code

#pragma once
#include <algorithm>
#include <limits>
#include <numeric>
#include <utility>

template <class T>
struct Add {
    using value_type = T;
    static constexpr T id() { return T(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs + rhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs + rhs;
    }
};

template <class T>
struct Mul {
    using value_type = T;
    static constexpr T id() { return T(1); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs * rhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs * rhs;
    }
};

template <class T>
struct And {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs & rhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs & rhs;
    }
};

template <class T>
struct Or {
    using value_type = T;
    static constexpr T id() { return T(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs | rhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs | rhs;
    }
};

template <class T>
struct Xor {
    using value_type = T;
    static constexpr T id() { return T(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs ^ rhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs ^ rhs;
    }
};

template <class T>
struct Min {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) { return std::min(lhs, rhs); }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return std::min((U)lhs, rhs);
    }
};

template <class T>
struct Max {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::lowest(); }
    static constexpr T op(const T &lhs, const T &rhs) { return std::max(lhs, rhs); }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return std::max((U)lhs, rhs);
    }
};

template <class T>
struct Gcd {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) {
        return lhs == Gcd::id() ? rhs : (rhs == Gcd::id() ? lhs : std::gcd(lhs, rhs));
    }
};

template <class T>
struct Lcm {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) {
        return lhs == Lcm::id() ? rhs : (rhs == Lcm::id() ? lhs : std::lcm(lhs, rhs));
    }
};

template <class T>
struct Update {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs == Update::id() ? rhs : lhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs == Update::id() ? rhs : lhs;
    }
};

template <class T>
struct Affine {
    using P = std::pair<T, T>;
    using value_type = P;
    static constexpr P id() { return P(1, 0); }
    static constexpr P op(P lhs, P rhs) { return {lhs.first * rhs.first, rhs.first * lhs.second + rhs.second}; }
};

template <class M>
struct Rev {
    using T = typename M::value_type;
    using value_type = T;
    static constexpr T id() { return M::id(); }
    static constexpr T op(T lhs, T rhs) { return M::op(rhs, lhs); }
};

#line 2 "lib/segtree/monoid.hpp"
#include <algorithm>
#include <limits>
#include <numeric>
#include <utility>

template <class T>
struct Add {
    using value_type = T;
    static constexpr T id() { return T(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs + rhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs + rhs;
    }
};

template <class T>
struct Mul {
    using value_type = T;
    static constexpr T id() { return T(1); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs * rhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs * rhs;
    }
};

template <class T>
struct And {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs & rhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs & rhs;
    }
};

template <class T>
struct Or {
    using value_type = T;
    static constexpr T id() { return T(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs | rhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs | rhs;
    }
};

template <class T>
struct Xor {
    using value_type = T;
    static constexpr T id() { return T(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs ^ rhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs ^ rhs;
    }
};

template <class T>
struct Min {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) { return std::min(lhs, rhs); }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return std::min((U)lhs, rhs);
    }
};

template <class T>
struct Max {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::lowest(); }
    static constexpr T op(const T &lhs, const T &rhs) { return std::max(lhs, rhs); }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return std::max((U)lhs, rhs);
    }
};

template <class T>
struct Gcd {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) {
        return lhs == Gcd::id() ? rhs : (rhs == Gcd::id() ? lhs : std::gcd(lhs, rhs));
    }
};

template <class T>
struct Lcm {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) {
        return lhs == Lcm::id() ? rhs : (rhs == Lcm::id() ? lhs : std::lcm(lhs, rhs));
    }
};

template <class T>
struct Update {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static constexpr T op(const T &lhs, const T &rhs) { return lhs == Update::id() ? rhs : lhs; }

    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs == Update::id() ? rhs : lhs;
    }
};

template <class T>
struct Affine {
    using P = std::pair<T, T>;
    using value_type = P;
    static constexpr P id() { return P(1, 0); }
    static constexpr P op(P lhs, P rhs) { return {lhs.first * rhs.first, rhs.first * lhs.second + rhs.second}; }
};

template <class M>
struct Rev {
    using T = typename M::value_type;
    using value_type = T;
    static constexpr T id() { return M::id(); }
    static constexpr T op(T lhs, T rhs) { return M::op(rhs, lhs); }
};

Back to top page