Strict Min 2 Monoid
(monoid/strict_min2.hpp)

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

Overview

A monoid that maintains the strictly smallest (opt1) and strictly second-smallest (opt2) values in a contiguous subarray. If all elements in the range are the same, opt2 will remain the identity element.

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

Example

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

using StrictMin2M = m1une::monoid::StrictMin2<long long>;

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

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

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

    auto res = seg.prod(0, 4); // Range: [3, 3, 5, 8]

    std::cout << "1st Min: " << res.opt1 << "\n"; // Output: 3
    std::cout << "2nd Min: " << res.opt2 << "\n"; // Output: 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.

Required by

• Strict Max 2 Monoid (monoid/strict_max2.hpp)

Verified with

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

Code

#ifndef M1UNE_MONOID_STRICT_MIN2_HPP
#define M1UNE_MONOID_STRICT_MIN2_HPP 1

#include <functional>
#include <limits>

namespace m1une {
namespace monoid {

template <typename T>
struct StrictOpt2Node {
    T opt1;  // The strictly best value
    T opt2;  // The strictly second-best value
};

// Monoid for finding the strictly 1st and 2nd optimal (minimum by default) values in a range.
template <typename T, T Id = std::numeric_limits<T>::max(), typename Compare = std::less<T>>
struct StrictMin2 {
    using value_type = StrictOpt2Node<T>;
    static constexpr bool commutative = true;

    // The identity element has both values set to Id.
    static constexpr value_type id() {
        return {Id, Id};
    }

    // Merges two elements, preserving the top 2 strictly unique values.
    static constexpr value_type op(const value_type& a, const value_type& b) {
        auto update = [](T& m1, T& m2, T val) {
            if (val == Id || val == m1 || val == m2) return;
            if (m1 == Id || Compare()(val, m1)) {
                m2 = m1;
                m1 = val;
            } else if (m2 == Id || Compare()(val, m2)) {
                m2 = val;
            }
        };

        T m1 = Id, m2 = Id;
        update(m1, m2, a.opt1);
        update(m1, m2, a.opt2);
        update(m1, m2, b.opt1);
        update(m1, m2, b.opt2);

        return {m1, m2};
    }

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

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_STRICT_MIN2_HPP

#line 1 "monoid/strict_min2.hpp"



#include <functional>
#include <limits>

namespace m1une {
namespace monoid {

template <typename T>
struct StrictOpt2Node {
    T opt1;  // The strictly best value
    T opt2;  // The strictly second-best value
};

// Monoid for finding the strictly 1st and 2nd optimal (minimum by default) values in a range.
template <typename T, T Id = std::numeric_limits<T>::max(), typename Compare = std::less<T>>
struct StrictMin2 {
    using value_type = StrictOpt2Node<T>;
    static constexpr bool commutative = true;

    // The identity element has both values set to Id.
    static constexpr value_type id() {
        return {Id, Id};
    }

    // Merges two elements, preserving the top 2 strictly unique values.
    static constexpr value_type op(const value_type& a, const value_type& b) {
        auto update = [](T& m1, T& m2, T val) {
            if (val == Id || val == m1 || val == m2) return;
            if (m1 == Id || Compare()(val, m1)) {
                m2 = m1;
                m1 = val;
            } else if (m2 == Id || Compare()(val, m2)) {
                m2 = val;
            }
        };

        T m1 = Id, m2 = Id;
        update(m1, m2, a.opt1);
        update(m1, m2, a.opt2);
        update(m1, m2, b.opt1);
        update(m1, m2, b.opt2);

        return {m1, m2};
    }

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

}  // namespace monoid
}  // namespace m1une

Back to top page