Range Multiply Range Sum
(acted_monoid/range_mul_range_sum.hpp)

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

Overview

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

Unlike Range Addition or Range Affine transformations, Range Multiplication distributes perfectly over addition: $C \times (A + B) = C \cdot A + C \cdot B$. Because of this mathematical property, the value_type does not need to store the size of the segment, making this monoid lighter in memory and faster to compute than the full RangeAffineRangeSum.

Template Parameters

• T: The underlying numerical type. It is strongly recommended to use a modular arithmetic struct (e.g., Modint) to prevent overflow, as repeated multiplications grow exponentially.

Example

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

// Assuming a modular arithmetic type or standard long long for small bounds
using AM = m1une::acted_monoid::RangeMulRangeSum<long long>;

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

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

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

    // Sum of range [0, 3) -> 2 + 3 + 4 = 9
    std::cout << "Initial Sum: " << seg.prod(0, 3) << "\n";

    // Multiply range [0, 2) by 5
    // Array becomes: {10, 15, 4, 1}
    seg.apply(0, 2, 5);

    // Sum of range [0, 3) -> 10 + 15 + 4 = 29
    std::cout << "Updated Sum: " << seg.prod(0, 3) << "\n";

    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.

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_MUL_RANGE_SUM_HPP
#define M1UNE_ACTED_MONOID_RANGE_MUL_RANGE_SUM_HPP 1

namespace m1une {
namespace acted_monoid {

// Acted Monoid for Range Multiplication and Range Sum queries.
// Operates natively on scalars or Modint classes without needing to track segment size.
template <typename T>
struct RangeMulRangeSum {
    using value_type = 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);
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return a + b;
    }

    // Operator Monoid (Multiply)
    static constexpr operator_type op_id() {
        return T(1);
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f * g;
    }

    // Mapping: Distribution Property ( f * (a+b) = f*a + f*b )
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        return f * x;
    }

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

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_MUL_RANGE_SUM_HPP

#line 1 "acted_monoid/range_mul_range_sum.hpp"



namespace m1une {
namespace acted_monoid {

// Acted Monoid for Range Multiplication and Range Sum queries.
// Operates natively on scalars or Modint classes without needing to track segment size.
template <typename T>
struct RangeMulRangeSum {
    using value_type = 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);
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return a + b;
    }

    // Operator Monoid (Multiply)
    static constexpr operator_type op_id() {
        return T(1);
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f * g;
    }

    // Mapping: Distribution Property ( f * (a+b) = f*a + f*b )
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        return f * x;
    }

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

}  // namespace acted_monoid
}  // namespace m1une

Back to top page