MinMax Monoid
(monoid/min_max.hpp)

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

Overview

A monoid for retrieving both the minimum and maximum values of a contiguous subarray in a single query. The underlying value_type is std::pair<T, T>, where first is the minimum value and second is the maximum value.

Initialization

Use the make(val) method to construct a leaf node from a single scalar value.

Example

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

using MinMaxM = m1une::monoid::MinMax<long long>;

int main() {
    std::vector<long long> A = {8, 2, 5, 3, 9, 1};
    int N = A.size();

    std::vector<MinMaxM::value_type> init_data(N);
    for (int i = 0; i < N; ++i) {
        init_data[i] = MinMaxM::make(A[i]);
    }

    m1une::ds::Segtree<MinMaxM> seg(init_data);

    // Query the range [1, 4) -> {2, 5, 3}
    auto [min_val, max_val] = seg.prod(1, 4);

    std::cout << "Min: " << min_val << ", Max: " << max_val << "\n"; // Output: Min: 2, Max: 5

    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.

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_MIN_MAX_HPP
#define M1UNE_MONOID_MIN_MAX_HPP 1

#include <algorithm>
#include <limits>
#include <utility>

namespace m1une {
namespace monoid {

// Monoid for finding both the minimum and maximum values in a range simultaneously.
template <typename T, T MinId = std::numeric_limits<T>::max(), T MaxId = std::numeric_limits<T>::lowest()>
struct MinMax {
    using value_type = std::pair<T, T>;
    static constexpr bool commutative = true;

    // The identity element contains the bounds for min and max.
    static constexpr value_type id() {
        return {MinId, MaxId};
    }

    // Merges two elements, extracting the overall min and max.
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {std::min(a.first, b.first), std::max(a.second, b.second)};
    }

    // Helper to securely create a leaf node from a single value.
    static constexpr value_type make(const T& val) {
        return {val, val};
    }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_MIN_MAX_HPP

#line 1 "monoid/min_max.hpp"



#include <algorithm>
#include <limits>
#include <utility>

namespace m1une {
namespace monoid {

// Monoid for finding both the minimum and maximum values in a range simultaneously.
template <typename T, T MinId = std::numeric_limits<T>::max(), T MaxId = std::numeric_limits<T>::lowest()>
struct MinMax {
    using value_type = std::pair<T, T>;
    static constexpr bool commutative = true;

    // The identity element contains the bounds for min and max.
    static constexpr value_type id() {
        return {MinId, MaxId};
    }

    // Merges two elements, extracting the overall min and max.
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {std::min(a.first, b.first), std::max(a.second, b.second)};
    }

    // Helper to securely create a leaf node from a single value.
    static constexpr value_type make(const T& val) {
        return {val, val};
    }
};

}  // namespace monoid
}  // namespace m1une

Back to top page