Range AP Add Range Sum
(acted_monoid/range_ap_add_range_sum.hpp)

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

Overview

An Acted Monoid that supports adding an arithmetic progression to a range, alongside range sum queries.

The operator is represented as a function $f(i) = a \cdot i + b$, where $i$ is the 0-based order inside the updated range.

Important Usage Note

The node state (value_type) stores size and the sum of relative orders (ord_sum) it covers. This makes it usable in dynamic arrays where global indices change after insertions, deletions, and reversals.

To apply a global formula on [l, r), convert it to range-local form first: a * global_i + b becomes a * local_i + (a * l + b).

Example

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

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

int main() {
    std::vector<long long> A = {0, 0, 0, 0, 0};
    m1une::ds::LazySegtree<AM> seg(A);

    // Add f(i) = 2 * i + 5 to the range [1, 4), where i is local to [1, 4)
    // Array becomes: {0, 5, 7, 9, 0}
    seg.apply(1, 4, {2, 5});

    // Query sum of range [0, 5) -> 0 + 5 + 7 + 9 + 0 = 21
    std::cout << seg.prod(0, 5).sum << "\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/ds/dynamic_array/dynamic_lazy_monoid_array_range_ap.test.cpp
• verify/ds/dynamic_array/persistent_dynamic_lazy_monoid_array_range_ap.test.cpp
• verify/ds/segtree/dynamic_lazy_segtree.test.cpp
• verify/ds/segtree/persistent_dynamic_lazy_segtree.test.cpp
• verify/ds/segtree/persistent_segtree_beats.test.cpp
• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_AP_ADD_RANGE_SUM_HPP
#define M1UNE_ACTED_MONOID_RANGE_AP_ADD_RANGE_SUM_HPP 1

#include <utility>

namespace m1une {
namespace acted_monoid {

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

template <typename T>
struct RangeApAddRangeSum {
    using value_type = RangeApAddRangeSumNode<T>;
    using operator_type = std::pair<T, T>;  // {a, b} for adding a * i + b
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = true;

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

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

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        return mapping(f, x, 0);
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x, long long ord) {
        return {x.sum + f.first * (x.ord_sum + T(ord) * T(x.size)) + f.second * T(x.size), x.size, x.ord_sum};
    }

    static constexpr operator_type op_shift(const operator_type& f, long long ord) {
        return {f.first, f.second + f.first * T(ord)};
    }

    static constexpr operator_type op_reverse(const operator_type& f, long long size) {
        return {-f.first, f.second + f.first * T(size - 1)};
    }

    static constexpr value_type make(const T& val) {
        return {val, 1, T(0)};
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_AP_ADD_RANGE_SUM_HPP

#line 1 "acted_monoid/range_ap_add_range_sum.hpp"



#include <utility>

namespace m1une {
namespace acted_monoid {

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

template <typename T>
struct RangeApAddRangeSum {
    using value_type = RangeApAddRangeSumNode<T>;
    using operator_type = std::pair<T, T>;  // {a, b} for adding a * i + b
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = true;

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

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

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        return mapping(f, x, 0);
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x, long long ord) {
        return {x.sum + f.first * (x.ord_sum + T(ord) * T(x.size)) + f.second * T(x.size), x.size, x.ord_sum};
    }

    static constexpr operator_type op_shift(const operator_type& f, long long ord) {
        return {f.first, f.second + f.first * T(ord)};
    }

    static constexpr operator_type op_reverse(const operator_type& f, long long size) {
        return {-f.first, f.second + f.first * T(size - 1)};
    }

    static constexpr value_type make(const T& val) {
        return {val, 1, T(0)};
    }
};

}  // namespace acted_monoid
}  // namespace m1une

Back to top page