Top K Count Monoid
(monoid/top_k_count.hpp)

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

Overview

A monoid that maintains the Top $K$ (largest) distinct elements and their frequencies (counts) in a range. The underlying value_type is std::vector<std::pair<T, int>>. Merging two nodes takes $O(K)$ time.

Initialization

Use the make(val) method to construct a leaf node containing a single value with a count of 1.

Example

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

// Define a monoid to keep the Top 2 distinct elements and their counts
using Top2CM = m1une::monoid::TopKCount<long long, 2>;

int main() {
    std::vector<long long> A = {10, 50, 50, 40, 50};
    int N = A.size();

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

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

    // Get the top 2 elements in the range [0, 5) -> { (50, 3), (40, 1) }
    auto top2 = seg.prod(0, 5);

    for (auto p : top2) {
        std::cout << "Value: " << p.first << " Count: " << p.second << "\n";
    }

    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_TOP_K_COUNT_HPP
#define M1UNE_MONOID_TOP_K_COUNT_HPP 1

#include <algorithm>
#include <functional>
#include <utility>
#include <vector>

namespace m1une {
namespace monoid {

// Monoid for finding the top K distinct elements and their frequencies in a range.
// The default Compare is std::greater<T> (descending order for Top K).
template <typename T, int K, typename Compare = std::greater<T>>
struct TopKCount {
    using value_type = std::vector<std::pair<T, int>>;
    static constexpr bool commutative = true;

    static constexpr value_type id() {
        return value_type();
    }

    static constexpr value_type op(const value_type& a, const value_type& b) {
        value_type res;
        res.reserve(std::min(K, (int)(a.size() + b.size())));

        int i = 0, j = 0;
        while (res.size() < (std::size_t)K && (i < (int)a.size() || j < (int)b.size())) {
            if (i == (int)a.size()) {
                res.push_back(b[j++]);
            } else if (j == (int)b.size()) {
                res.push_back(a[i++]);
            } else if (a[i].first == b[j].first) {
                // If the values are identical, merge their counts
                res.push_back({a[i].first, a[i].second + b[j].second});
                i++;
                j++;
            } else if (Compare()(a[i].first, b[j].first)) {
                res.push_back(a[i++]);
            } else {
                res.push_back(b[j++]);
            }
        }
        return res;
    }

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

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_TOP_K_COUNT_HPP

#line 1 "monoid/top_k_count.hpp"



#include <algorithm>
#include <functional>
#include <utility>
#include <vector>

namespace m1une {
namespace monoid {

// Monoid for finding the top K distinct elements and their frequencies in a range.
// The default Compare is std::greater<T> (descending order for Top K).
template <typename T, int K, typename Compare = std::greater<T>>
struct TopKCount {
    using value_type = std::vector<std::pair<T, int>>;
    static constexpr bool commutative = true;

    static constexpr value_type id() {
        return value_type();
    }

    static constexpr value_type op(const value_type& a, const value_type& b) {
        value_type res;
        res.reserve(std::min(K, (int)(a.size() + b.size())));

        int i = 0, j = 0;
        while (res.size() < (std::size_t)K && (i < (int)a.size() || j < (int)b.size())) {
            if (i == (int)a.size()) {
                res.push_back(b[j++]);
            } else if (j == (int)b.size()) {
                res.push_back(a[i++]);
            } else if (a[i].first == b[j].first) {
                // If the values are identical, merge their counts
                res.push_back({a[i].first, a[i].second + b[j].second});
                i++;
                j++;
            } else if (Compare()(a[i].first, b[j].first)) {
                res.push_back(a[i++]);
            } else {
                res.push_back(b[j++]);
            }
        }
        return res;
    }

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

}  // namespace monoid
}  // namespace m1une

Back to top page