Range AP Update Range Sum
(acted_monoid/range_ap_update_range_sum.hpp)
- View this file on GitHub
- Last update: 2026-07-21 20:17:47+09:00
- Include:
#include "acted_monoid/range_ap_update_range_sum.hpp"
Overview
An Acted Monoid that supports overwriting a range with an arithmetic progression, alongside range sum queries.
The operator replaces existing elements with $f(i) = a \cdot i + b$, where $i$ is the 0-based order inside the updated range.
Important Usage Note
Similar to RangeApAddRangeSum, the node state (value_type) tracks size and the sum of relative orders (ord_sum), enabling $O(1)$ block updates.
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). The operator_type relies on std::optional to safely designate the “no operation” state.
Example
#include "ds/segtree/lazy_segtree.hpp"
#include "acted_monoid/range_ap_update_range_sum.hpp"
#include <iostream>
#include <vector>
using AM = m1une::acted_monoid::RangeApUpdateRangeSum<long long>;
int main() {
std::vector<long long> A = {10, 20, 30, 40, 50};
m1une::ds::LazySegtree<AM> seg(A);
// Overwrite the range [0, 3) with f(i) = 3 * i + 1, where i is local to [0, 3)
// Array becomes: {1, 4, 7, 40, 50}
seg.apply(0, 3, std::optional<std::pair<long long, long long>>({3, 1}));
// Query sum of range [0, 3) -> 1 + 4 + 7 = 12
std::cout << seg.prod(0, 3).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
Code
#ifndef M1UNE_ACTED_MONOID_RANGE_AP_UPDATE_RANGE_SUM_HPP
#define M1UNE_ACTED_MONOID_RANGE_AP_UPDATE_RANGE_SUM_HPP 1
#include <optional>
#include <utility>
namespace m1une {
namespace acted_monoid {
template <typename T>
struct RangeApUpdateRangeSumNode {
T sum;
long long size;
T ord_sum;
};
template <typename T>
struct RangeApUpdateRangeSum {
using value_type = RangeApUpdateRangeSumNode<T>;
using operator_type = std::optional<std::pair<T, T>>; // {a, b} for setting to a * i + b
static constexpr bool commutative = false;
static constexpr bool operator_commutative = false;
// 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 (Update)
static constexpr operator_type op_id() {
return std::nullopt;
}
static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
// Prioritize the newer operation (f) over the older one (g)
return f.has_value() ? f : g;
}
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) {
if (!f.has_value() || x.size == 0) return x;
return {f.value().first * (x.ord_sum + T(ord) * T(x.size)) + f.value().second * T(x.size), x.size,
x.ord_sum};
}
static constexpr operator_type op_shift(const operator_type& f, long long ord) {
if (!f.has_value()) return f;
return std::pair<T, T>{f.value().first, f.value().second + f.value().first * T(ord)};
}
static constexpr operator_type op_reverse(const operator_type& f, long long size) {
if (!f.has_value()) return f;
return std::pair<T, T>{-f.value().first, f.value().second + f.value().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_UPDATE_RANGE_SUM_HPP#line 1 "acted_monoid/range_ap_update_range_sum.hpp"
#include <optional>
#include <utility>
namespace m1une {
namespace acted_monoid {
template <typename T>
struct RangeApUpdateRangeSumNode {
T sum;
long long size;
T ord_sum;
};
template <typename T>
struct RangeApUpdateRangeSum {
using value_type = RangeApUpdateRangeSumNode<T>;
using operator_type = std::optional<std::pair<T, T>>; // {a, b} for setting to a * i + b
static constexpr bool commutative = false;
static constexpr bool operator_commutative = false;
// 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 (Update)
static constexpr operator_type op_id() {
return std::nullopt;
}
static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
// Prioritize the newer operation (f) over the older one (g)
return f.has_value() ? f : g;
}
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) {
if (!f.has_value() || x.size == 0) return x;
return {f.value().first * (x.ord_sum + T(ord) * T(x.size)) + f.value().second * T(x.size), x.size,
x.ord_sum};
}
static constexpr operator_type op_shift(const operator_type& f, long long ord) {
if (!f.has_value()) return f;
return std::pair<T, T>{f.value().first, f.value().second + f.value().first * T(ord)};
}
static constexpr operator_type op_reverse(const operator_type& f, long long size) {
if (!f.has_value()) return f;
return std::pair<T, T>{-f.value().first, f.value().second + f.value().first * T(size - 1)};
}
static constexpr value_type make(const T& val) {
return {val, 1, T(0)};
}
};
} // namespace acted_monoid
} // namespace m1une