ArgMin Monoid
(monoid/arg_min.hpp)

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

Overview

A monoid for finding both the minimum value and its relative order in a range. If there are multiple minimum values, it returns the earliest one.

For the maximum counterpart, see monoid/arg_max.hpp.

Example

#include "ds/segtree/segtree.hpp"
#include "monoid/arg_min.hpp"
#include <iostream>
#include <vector>

using ArgMinM = m1une::monoid::ArgMin<long long>;

int main() {
    std::vector<long long> A = {4, 2, 5, 2, 8};
    m1une::ds::Segtree<ArgMinM> seg(A);

    auto res = seg.prod(0, A.size());

    std::cout << "Min Value: " << res.value << "\n"; // Output: 2
    std::cout << "Order: " << res.ord << "\n";       // Output: 1 (Order 1 is chosen over order 3)

    return 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

• Range Add Range ArgMin (acted_monoid/range_add_range_arg_min.hpp)
• ArgMax Monoid (monoid/arg_max.hpp)

Verified with

• verify/monoid/commutative_flags.test.cpp
• verify/monoid/commutative_flags.test.cpp
• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_ARG_MIN_HPP
#define M1UNE_MONOID_ARG_MIN_HPP 1

#include <functional>
#include <limits>

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

#endif  // M1UNE_MONOID_ARG_MIN_HPP

#line 1 "monoid/arg_min.hpp"



#include <functional>
#include <limits>

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

Back to top page