Range Add Range Min Count
(acted_monoid/range_add_range_min_count.hpp)

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

Overview

An Acted Monoid that supports range addition queries and can dynamically track both the minimum value and its frequency (count) in a range.

Adding a uniform constant to a range shifts all elements by the same amount. Because relative differences remain unchanged, the count of the minimum element stays exactly the same, allowing the mapping operation to be performed in $O(1)$ time.

By reusing m1une::monoid::MinCount, this structure can easily be converted to Range Add Range Max Count by passing std::greater<T> as the comparison functor.

Template Parameters

• T: The underlying scalar type (e.g., long long).
• Id: The identity element for the value. Defaults to std::numeric_limits<T>::max().
• Compare: The comparison functor. Defaults to std::less<T>.

Example

#include "ds/segtree/lazy_segtree.hpp"
#include "acted_monoid/range_add_range_min_count.hpp"
#include <iostream>
#include <vector>

using AM = m1une::acted_monoid::RangeAddRangeMinCount<long long>;

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

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

    m1une::ds::LazySegtree<AM> seg(init_nodes);

    // Initial min is 4, appearing 2 times
    auto q1 = seg.prod(0, N);
    std::cout << "Min: " << q1.first << ", Count: " << q1.second << "\n"; // Output: Min: 4, Count: 2

    // Add 10 to range [0, 3) -> {18, 14, 19, 4, 7}
    seg.apply(0, 3, 10);

    // New min is 4, appearing 1 time
    auto q2 = seg.prod(0, N);
    std::cout << "Min: " << q2.first << ", Count: " << q2.second << "\n"; // Output: Min: 4, Count: 1

    return 0;
}

Interface and Complexity

This is a stateless acted-monoid tag. Lazy data structures use its public value_type, operator_type, id(), op(a, b), op_id(), op_comp(f, g), and mapping(f, x) members. Helpers such as make(...), shifted mappings, or reversal-aware mappings are described above when the header provides them.

The static operations are $O(1)$ for the scalar metadata stored by these range acted monoids, aside from the cost of the underlying arithmetic type.

Depends on

• MinCount Monoid (monoid/min_count.hpp)

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_MIN_COUNT_HPP
#define M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_MIN_COUNT_HPP 1

#include <functional>
#include <limits>

#include "../monoid/min_count.hpp"

namespace m1une {
namespace acted_monoid {

template <typename T, T Id = std::numeric_limits<T>::max(), typename Compare = std::less<T>>
struct RangeAddRangeMinCount {
    using BaseMonoid = m1une::monoid::MinCount<T, Id, Compare>;
    using value_type = typename BaseMonoid::value_type;  // std::pair<T, int>
    using operator_type = T;
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = true;

    // Value Monoid (Min Count)
    static constexpr value_type id() {
        return BaseMonoid::id();
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return BaseMonoid::op(a, b);
    }

    // Operator Monoid (Add)
    static constexpr operator_type op_id() {
        return T(0);
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f + g;
    }

    // Mapping
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (x.second == 0) return x;  // Do not apply to the identity element
        return {x.first + f, x.second};
    }

    // Helper for initializing a leaf node
    static constexpr value_type make(const T& val, int count = 1) {
        return BaseMonoid::make(val, count);
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_MIN_COUNT_HPP

#line 1 "acted_monoid/range_add_range_min_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 "acted_monoid/range_add_range_min_count.hpp"

namespace m1une {
namespace acted_monoid {

template <typename T, T Id = std::numeric_limits<T>::max(), typename Compare = std::less<T>>
struct RangeAddRangeMinCount {
    using BaseMonoid = m1une::monoid::MinCount<T, Id, Compare>;
    using value_type = typename BaseMonoid::value_type;  // std::pair<T, int>
    using operator_type = T;
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = true;

    // Value Monoid (Min Count)
    static constexpr value_type id() {
        return BaseMonoid::id();
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return BaseMonoid::op(a, b);
    }

    // Operator Monoid (Add)
    static constexpr operator_type op_id() {
        return T(0);
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f + g;
    }

    // Mapping
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (x.second == 0) return x;  // Do not apply to the identity element
        return {x.first + f, x.second};
    }

    // Helper for initializing a leaf node
    static constexpr value_type make(const T& val, int count = 1) {
        return BaseMonoid::make(val, count);
    }
};

}  // namespace acted_monoid
}  // namespace m1une

Back to top page