Add Monoid
(monoid/add.hpp)

• View this file on GitHub
• Last update: 2026-07-21 20:17:47+09:00
• Include: #include "monoid/add.hpp"

Overview

A monoid representing the addition operation. It is commonly used with Segment Trees or Lazy Segment Trees for Range Sum Queries.

Template Parameters

• T: The underlying numeric data type (e.g., long long, int, or Modint).

Properties

• Operation: Addition ($a + b$)
• Identity Element: $0$

Interface and Complexity

This is a stateless algebra tag. Generic data structures use its public value_type, id(), and op(a, b) members. If the type also provides helpers such as make(...) or inv(x), they are described above or in the documented properties.

Each static operation runs in the cost of the underlying operation shown in the properties. Scalar monoids are $O(1)$; monoids whose value_type stores several items, permutations, or matrices scale with that stored size.

Required by

• Dynamic Connectivity (ds/dynamic_connectivity/all.hpp)
• Online Dynamic Connectivity (ds/dynamic_connectivity/online_dynamic_connectivity.hpp)
• Graph All (graph/all.hpp)
• Tree All (graph/tree/all.hpp)
• Tree Cumulative Sum (graph/tree/cumulative_sum.hpp)
• Range Contour Query on Tree (graph/tree/range_contour_query.hpp)
• Tree (graph/tree/tree.hpp)

Verified with

• verify/ds/binary_trie/binary_trie_monoid.test.cpp
• verify/ds/dsu/dsu_monoid.test.cpp
• verify/ds/dsu/persistent_potentialized_dsu.test.cpp
• verify/ds/dsu/potentialized_dsu.test.cpp
• verify/ds/dsu/rollback_potentialized_dsu.test.cpp
• verify/ds/dynamic_array/dynamic_monoid_array.test.cpp
• verify/ds/dynamic_array/persistent_dynamic_monoid_array.test.cpp
• verify/ds/dynamic_connectivity/dynamic_connectivity.test.cpp
• verify/ds/dynamic_tree/link_cut_tree.test.cpp
• verify/ds/dynamic_tree/path_link_cut_tree.test.cpp
• verify/ds/persistent_cow.test.cpp
• verify/ds/persistent_release.test.cpp
• verify/ds/range_query/disjoint_sparse_table.test.cpp
• verify/ds/range_query/sqrt_tree.test.cpp
• verify/ds/rollback_counterparts.test.cpp
• verify/ds/segtree/dual_segtree_2d.test.cpp
• verify/ds/segtree/dynamic_dual_segtree.test.cpp
• verify/ds/segtree/dynamic_segtree.test.cpp
• verify/ds/segtree/persistent_dual_segtree.test.cpp
• verify/ds/segtree/persistent_dynamic_dual_segtree.test.cpp
• verify/ds/segtree/persistent_dynamic_segtree.test.cpp
• verify/ds/segtree/persistent_segtree.test.cpp
• verify/ds/segtree/segtree.test.cpp
• verify/ds/segtree/segtree_2d.test.cpp
• verify/graph/cow_game.test.cpp
• verify/graph/graph_algorithms.test.cpp
• verify/graph/range_edge_graph.test.cpp
• verify/graph/tree/tree_algorithms.test.cpp
• verify/graph/tree/tree_cumulative_sum.test.cpp
• verify/graph/tree/vertex_add_range_contour_sum_on_tree.test.cpp
• verify/graph/tree/vertex_get_range_contour_add_on_tree.test.cpp
• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_ADD_HPP
#define M1UNE_MONOID_ADD_HPP 1

namespace m1une {
namespace monoid {

// Monoid for addition (Range Sum).
template <typename T>
struct Add {
    using value_type = T;
    static constexpr bool commutative = true;

    // Returns the identity element for addition, which is 0.
    static constexpr T id() {
        return T(0);
    }

    // Returns the sum of a and b.
    static constexpr T op(const T& a, const T& b) {
        return a + b;
    }

    static constexpr T inv(const T& x) {
        return -x;
    }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_ADD_HPP

#line 1 "monoid/add.hpp"



namespace m1une {
namespace monoid {

// Monoid for addition (Range Sum).
template <typename T>
struct Add {
    using value_type = T;
    static constexpr bool commutative = true;

    // Returns the identity element for addition, which is 0.
    static constexpr T id() {
        return T(0);
    }

    // Returns the sum of a and b.
    static constexpr T op(const T& a, const T& b) {
        return a + b;
    }

    static constexpr T inv(const T& x) {
        return -x;
    }
};

}  // namespace monoid
}  // namespace m1une

Back to top page