Range Add Range Sum
(acted_monoid/range_add_range_sum.hpp)

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

Overview

An Acted Monoid representing Range Addition operations and Range Sum queries.

Important Usage Note

When adding a value $f$ to a range of sum $x$, the total sum increases by $f \times (\text{length of the range})$. Therefore, the value_type cannot just be an integer; it must keep track of the size of the range it currently represents.

The value_type is defined as RangeAddRangeSumNode<T>, which holds both the sum and the size.

When initializing a data structure (like a Lazy Segment Tree) with this acted monoid, you must initialize the leaf nodes with size = 1. You can use the helper function make(val) for this purpose.

Example

// Assuming `lazy_segtree` is implemented
std::vector<m1une::acted_monoid::RangeAddRangeSumNode<long long>> init_nodes(N);
for (int i = 0; i < N; ++i) {
    // Initialize each leaf with the value and size = 1
    init_nodes[i] = m1une::acted_monoid::RangeAddRangeSum<long long>::make(A[i]);
}

lazy_segtree<RangeAddRangeSum<long long>> seg(init_nodes);

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.

Verified with

• verify/ds/dynamic_array/persistent_dynamic_lazy_monoid_array.test.cpp
• verify/ds/dynamic_tree/lazy_link_cut_tree.test.cpp
• verify/ds/dynamic_tree/lazy_path_link_cut_tree.test.cpp
• verify/ds/persistent_cow.test.cpp
• verify/ds/persistent_release.test.cpp
• verify/ds/rollback_counterparts.test.cpp
• verify/ds/segtree/dynamic_lazy_segtree.test.cpp
• verify/ds/segtree/persistent_dynamic_lazy_segtree.test.cpp
• verify/ds/segtree/persistent_lazy_segtree.test.cpp
• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_SUM_HPP
#define M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_SUM_HPP 1

namespace m1une {
namespace acted_monoid {

template <typename T>
struct RangeAddRangeSumNode {
    T sum;
    long long size;
};

template <typename T>
struct RangeAddRangeSum {
    using value_type = RangeAddRangeSumNode<T>;
    using operator_type = T;
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = true;

    // Value Monoid (Sum)
    static constexpr value_type id() {
        return {T(0), 0};
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {a.sum + b.sum, a.size + b.size};
    }
    static constexpr value_type inv(const value_type& x) {
        return {-x.sum, -x.size};
    }

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

    // Mapping (sum + f * size)
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        return {x.sum + f * x.size, x.size};
    }

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

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_SUM_HPP

#line 1 "acted_monoid/range_add_range_sum.hpp"



namespace m1une {
namespace acted_monoid {

template <typename T>
struct RangeAddRangeSumNode {
    T sum;
    long long size;
};

template <typename T>
struct RangeAddRangeSum {
    using value_type = RangeAddRangeSumNode<T>;
    using operator_type = T;
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = true;

    // Value Monoid (Sum)
    static constexpr value_type id() {
        return {T(0), 0};
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {a.sum + b.sum, a.size + b.size};
    }
    static constexpr value_type inv(const value_type& x) {
        return {-x.sum, -x.size};
    }

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

    // Mapping (sum + f * size)
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        return {x.sum + f * x.size, x.size};
    }

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

}  // namespace acted_monoid
}  // namespace m1une

Back to top page