MaxCount Monoid
(monoid/max_count.hpp)

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

Overview

A monoid for finding both the maximum value and the frequency (count) of that maximum value in a range. The underlying value_type is std::pair<T, int>, where first is the value and second is the count.

This is the maximum counterpart to monoid/min_count.hpp.

Initialization

When initializing a segment tree from an array of elements, use the make(val) method to construct a leaf node with a default count of 1.

Example

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

using MaxCountM = m1une::monoid::MaxCount<long long>;

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

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

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

    // Query the range [0, 6) -> Elements: {3, 9, 4, 9, 5, 9}
    // Maximum is 9, it appears 3 times.
    auto [max_val, count] = seg.prod(0, 6);
    std::cout << "Max: " << max_val << ", Count: " << count << "\n"; // Output: Max: 9, Count: 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.

Depends on

• MinCount Monoid (monoid/min_count.hpp)

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_MAX_COUNT_HPP
#define M1UNE_MONOID_MAX_COUNT_HPP 1

#include <functional>
#include <limits>

#include "min_count.hpp"

namespace m1une {
namespace monoid {

// Monoid for finding the maximum value and its frequency in a range.
// Defined as a type alias of MinCount using std::greater.
template <typename T, T Id = std::numeric_limits<T>::lowest()>
using MaxCount = MinCount<T, Id, std::greater<T>>;

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_MAX_COUNT_HPP

#line 1 "monoid/max_count.hpp"



#include <functional>
#include <limits>

#line 1 "monoid/min_count.hpp"



#line 6 "monoid/min_count.hpp"
#include <utility>

namespace m1une {
namespace monoid {

// Monoid for finding the optimal value and its frequency in a range.
// Uses a comparison functor (Compare) to determine the optimal value (default is less, i.e., minimum).
template <typename T, T Id = std::numeric_limits<T>::max(), typename Compare = std::less<T>>
struct MinCount {
    using value_type = std::pair<T, int>;
    static constexpr bool commutative = true;

    // The identity element has the specified Id value and a count of 0.
    static constexpr value_type id() {
        return {Id, 0};
    }

    // Combines two elements, updating the optimal value and summing the counts if they are equal.
    static constexpr value_type op(const value_type& a, const value_type& b) {
        if (Compare()(a.first, b.first)) return a;
        if (Compare()(b.first, a.first)) return b;
        return {a.first, a.second + b.second};
    }

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

}  // namespace monoid
}  // namespace m1une


#line 8 "monoid/max_count.hpp"

namespace m1une {
namespace monoid {

// Monoid for finding the maximum value and its frequency in a range.
// Defined as a type alias of MinCount using std::greater.
template <typename T, T Id = std::numeric_limits<T>::lowest()>
using MaxCount = MinCount<T, Id, std::greater<T>>;

}  // namespace monoid
}  // namespace m1une

Back to top page