Range Add Range ArgMin
(acted_monoid/range_add_range_arg_min.hpp)

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

Overview

An Acted Monoid that supports range addition queries and can dynamically track both the minimum value and its relative order in a range.

Adding a uniform constant to a range shifts all elements by the same amount, meaning the relative ordering remains unchanged.

By reusing m1une::monoid::ArgMin, this structure resolves ties by prioritizing the earlier order.

Template Parameters

• T: The underlying scalar type (e.g., long long).
• Id: The identity element for the value. Defaults to std::numeric_limits<T>::max().
• Compare: The comparison functor. Defaults to std::less<T>. To build a Range Add Range ArgMax, simply pass std::greater<T>.

Example

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

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

int main() {
    std::vector<long long> A = {8, 4, 9, 4, 7};
    m1une::ds::LazySegtree<AM> seg(A);

    // Initial min is 4 at order 1 (ties broken by earlier order)
    auto q1 = seg.prod(0, A.size());
    std::cout << "Min: " << q1.value << ", Order: " << q1.ord << "\n"; // Output: Min: 4, Order: 1

    // Add 10 to range [0, 3) -> {18, 14, 19, 4, 7}
    seg.apply(0, 3, 10);

    // New min is 4 at order 3
    auto q2 = seg.prod(0, A.size());
    std::cout << "Min: " << q2.value << ", Order: " << q2.ord << "\n"; // Output: Min: 4, Order: 3

    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.

Depends on

• ArgMin Monoid (monoid/arg_min.hpp)

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_ARG_MIN_HPP
#define M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_ARG_MIN_HPP 1

#include <functional>
#include <limits>

#include "../monoid/arg_min.hpp"

namespace m1une {
namespace acted_monoid {

template <typename T, T Id = std::numeric_limits<T>::max(), typename Compare = std::less<T>>
struct RangeAddRangeArgMin {
    using BaseMonoid = m1une::monoid::ArgMin<T, Id, Compare>;
    using value_type = typename BaseMonoid::value_type;
    using operator_type = T;
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = true;

    // Value Monoid (ArgMin)
    static constexpr value_type id() {
        return BaseMonoid::id();
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return BaseMonoid::op(a, b);
    }

    // Operator Monoid (Add)
    static constexpr operator_type op_id() {
        return T(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.size == 0) return x;
        return {x.value + f, x.size, x.ord};
    }

    // Helper for initializing a leaf node
    static constexpr value_type make(const T& val) {
        return BaseMonoid::make(val);
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_ARG_MIN_HPP

#line 1 "acted_monoid/range_add_range_arg_min.hpp"



#include <functional>
#include <limits>

#line 1 "monoid/arg_min.hpp"



#line 6 "monoid/arg_min.hpp"

namespace m1une {
namespace monoid {

template <typename T>
struct ArgMinNode {
    T value;
    long long size;
    long long ord;
};

// Monoid for finding the optimal value (minimum by default) and its relative order.
// Ties are broken by choosing the earlier element.
template <typename T, T Id = std::numeric_limits<T>::max(), typename Compare = std::less<T>>
struct ArgMin {
    using value_type = ArgMinNode<T>;
    static constexpr bool commutative = false;

    static constexpr value_type id() {
        return {Id, 0, -1};
    }

    static constexpr value_type op(const value_type& a, const value_type& b) {
        if (a.size == 0) return b;
        if (b.size == 0) return a;
        long long size = a.size + b.size;
        if (Compare()(a.value, b.value)) return {a.value, size, a.ord};
        if (Compare()(b.value, a.value)) return {b.value, size, b.ord + a.size};
        return {a.value, size, a.ord};
    }

    static constexpr value_type make(const T& val) {
        return {val, 1, 0};
    }
};

}  // namespace monoid
}  // namespace m1une


#line 8 "acted_monoid/range_add_range_arg_min.hpp"

namespace m1une {
namespace acted_monoid {

template <typename T, T Id = std::numeric_limits<T>::max(), typename Compare = std::less<T>>
struct RangeAddRangeArgMin {
    using BaseMonoid = m1une::monoid::ArgMin<T, Id, Compare>;
    using value_type = typename BaseMonoid::value_type;
    using operator_type = T;
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = true;

    // Value Monoid (ArgMin)
    static constexpr value_type id() {
        return BaseMonoid::id();
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return BaseMonoid::op(a, b);
    }

    // Operator Monoid (Add)
    static constexpr operator_type op_id() {
        return T(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.size == 0) return x;
        return {x.value + f, x.size, x.ord};
    }

    // Helper for initializing a leaf node
    static constexpr value_type make(const T& val) {
        return BaseMonoid::make(val);
    }
};

}  // namespace acted_monoid
}  // namespace m1une

Back to top page