Top K Monoid
(monoid/top_k.hpp)

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

Overview

A monoid that maintains the Top $K$ (largest) elements in a range. The underlying value_type is std::vector<T>. Merging two nodes takes $O(K)$ time, so $K$ should be relatively small (e.g., $K \le 10$).

Initialization

Since the state is a std::vector<T>, you can use the make(val) helper to automatically wrap a single array element into a vector of size 1.

Example

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

// Define a monoid to keep the Top 3 elements
using Top3M = m1une::monoid::TopK<long long, 3>;

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

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

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

    // Get the top 3 elements in the range [0, 4) -> {50, 40, 20}
    std::vector<long long> top3 = seg.prod(0, 4);

    for (long long x : top3) {
        std::cout << x << " ";
    }
    std::cout << "\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.

Required by

• Bottom K Monoid (monoid/bottom_k.hpp)

Verified with

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

Code

#ifndef M1UNE_MONOID_TOP_K_HPP
#define M1UNE_MONOID_TOP_K_HPP 1

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

namespace m1une {
namespace monoid {

// Monoid for finding the top/bottom K elements in a range.
// The elements must be stored in the order defined by the Compare functor.
// Default Compare is std::greater<T> (i.e., descending order for Top K).
template <typename T, int K, typename Compare = std::greater<T>>
struct TopK {
    using value_type = std::vector<T>;
    static constexpr bool commutative = true;

    // The identity element is an empty vector.
    static constexpr value_type id() {
        return std::vector<T>();
    }

    // Merges two sorted vectors and keeps only the first K elements.
    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 (Compare()(a[i], b[j])) {
                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) {
        return {val};
    }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_TOP_K_HPP

#line 1 "monoid/top_k.hpp"



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

namespace m1une {
namespace monoid {

// Monoid for finding the top/bottom K elements in a range.
// The elements must be stored in the order defined by the Compare functor.
// Default Compare is std::greater<T> (i.e., descending order for Top K).
template <typename T, int K, typename Compare = std::greater<T>>
struct TopK {
    using value_type = std::vector<T>;
    static constexpr bool commutative = true;

    // The identity element is an empty vector.
    static constexpr value_type id() {
        return std::vector<T>();
    }

    // Merges two sorted vectors and keeps only the first K elements.
    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 (Compare()(a[i], b[j])) {
                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) {
        return {val};
    }
};

}  // namespace monoid
}  // namespace m1une

Back to top page