Range Add Range Min
(acted_monoid/range_add_range_min.hpp)

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

Overview

An Acted Monoid representing Range Addition operations and Range Minimum queries. It safely handles the identity element to prevent wrapping or incorrect modifications on uninitialized values.

Template Parameters

• T: The underlying scalar data type (e.g., long long, int).
• Id: The identity element for the value monoid. Defaults to std::numeric_limits<T>::max().

Example

#include "ds/segtree/lazy_segtree.hpp"
#include "acted_monoid/range_add_range_min.hpp"
#include <iostream>
#include <vector>

using AM = m1une::acted_monoid::RangeAddRangeMin<long long>;

int main() {
    std::vector<long long> A = {10, 20, 30, 40, 50};
    m1une::ds::LazySegtree<AM> seg(A);

    // Add -15 to all elements in range [1, 4) -> {10, 5, 15, 25, 50}
    seg.apply(1, 4, -15);

    // Get the minimum in range [0, 3) -> min(10, 5, 15) = 5
    std::cout << seg.prod(0, 3) << "\n";

    return 0;
}

Interface and Complexity

This is a stateless acted-monoid tag. Lazy data structures use its public value_type, operator_type, id(), op(a, b), op_id(), op_comp(f, g), and mapping(f, x) members. Helpers such as make(...), shifted mappings, or reversal-aware mappings are described above when the header provides them.

The static operations are $O(1)$ for the scalar metadata stored by these range acted monoids, aside from the cost of the underlying arithmetic type.

Verified with

• verify/ds/segtree/range_add_range_min.test.cpp
• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_MIN_HPP
#define M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_MIN_HPP 1

#include <algorithm>
#include <limits>

namespace m1une {
namespace acted_monoid {

template <typename T, T Id = std::numeric_limits<T>::max()>
struct RangeAddRangeMin {
    using value_type = T;
    using operator_type = T;
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = true;

    // Value Monoid (Min)
    static constexpr value_type id() {
        return Id;
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return std::min(a, b);
    }

    // Operator Monoid (Add)
    static constexpr operator_type op_id() {
        return 0;
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f + g;
    }

    // Mapping
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (x == id()) return x;  // Do not apply the operator to the identity element
        return x + f;
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_MIN_HPP

#line 1 "acted_monoid/range_add_range_min.hpp"



#include <algorithm>
#include <limits>

namespace m1une {
namespace acted_monoid {

template <typename T, T Id = std::numeric_limits<T>::max()>
struct RangeAddRangeMin {
    using value_type = T;
    using operator_type = T;
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = true;

    // Value Monoid (Min)
    static constexpr value_type id() {
        return Id;
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return std::min(a, b);
    }

    // Operator Monoid (Add)
    static constexpr operator_type op_id() {
        return 0;
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f + g;
    }

    // Mapping
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (x == id()) return x;  // Do not apply the operator to the identity element
        return x + f;
    }
};

}  // namespace acted_monoid
}  // namespace m1une

Back to top page