m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Range Affine Range Sum
(acted_monoid/range_affine_range_sum.hpp)

Overview

An Acted Monoid representing Range Affine Transformations ($f(x) = ax + b$) and Range Sum queries. It is commonly used with modular arithmetic (Modint) or standard scalar types.

Important Usage Note

When applying an affine transformation $f(x) = ax + b$ to a range of elements, the new sum becomes $a \times \text{sum} + b \times \text{size}$. Therefore, the value_type must keep track of the size of the range it currently represents.

The value_type is defined as RangeAffineRangeSumNode<T>, which holds T sum and int size.

When initializing a Lazy Segment Tree, you must initialize the leaf nodes with size = 1. Always use the helper function make(val) for this purpose.

Example

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

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

int main() {
    int N = 3;
    std::vector<AM::value_type> init_nodes(N);
    for (int i = 0; i < N; ++i) {
        // Initialize each leaf with the value and size = 1
        init_nodes[i] = AM::make(i + 1); // Array: {1, 2, 3}
    }

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

    // Apply f(x) = 2x + 3 to range [0, 2)
    // Elements become: (2*1 + 3) = 5, and (2*2 + 3) = 7 -> Array: {5, 7, 3}
    seg.apply(0, 2, {2, 3});

    // Get the sum of range [0, 3) -> 5 + 7 + 3 = 15
    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.

Member Description Complexity
static constexpr bool commutative true; allows compatible dynamic sequences to omit a reversed aggregate. $O(1)$
static constexpr int size(const value_type& value) Returns value.size. $O(1)$
static constexpr value_type make(const T& val) Constructs a leaf with sum val and size 1. $O(1)$

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_AFFINE_RANGE_SUM_HPP
#define M1UNE_ACTED_MONOID_RANGE_AFFINE_RANGE_SUM_HPP 1

#include <utility>

namespace m1une {
namespace acted_monoid {

template <typename T>
struct RangeAffineRangeSumNode {
    T sum;
    int size;
};

// Designed to accept Modint or similar types as T
template <typename T>
struct RangeAffineRangeSum {
    using value_type = RangeAffineRangeSumNode<T>;
    using operator_type = std::pair<T, T>;  // {a, b} for ax + b
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = false;

    // Value Monoid
    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 int size(const value_type& value) {
        return value.size;
    }

    // Operator Monoid (Affine Composition)
    // f(x) = a1*x + b1, g(x) = a2*x + b2
    // f(g(x)) = a1*(a2*x + b2) + b1 = (a1*a2)*x + (a1*b2 + b1)
    static constexpr operator_type op_id() {
        return {T(1), T(0)};
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return {f.first * g.first, f.first * g.second + f.second};
    }

    // Mapping
    // \sum (a*x_i + b) = a * \sum x_i + b * size
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        return {f.first * x.sum + f.second * T(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_AFFINE_RANGE_SUM_HPP
#line 1 "acted_monoid/range_affine_range_sum.hpp"



#include <utility>

namespace m1une {
namespace acted_monoid {

template <typename T>
struct RangeAffineRangeSumNode {
    T sum;
    int size;
};

// Designed to accept Modint or similar types as T
template <typename T>
struct RangeAffineRangeSum {
    using value_type = RangeAffineRangeSumNode<T>;
    using operator_type = std::pair<T, T>;  // {a, b} for ax + b
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = false;

    // Value Monoid
    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 int size(const value_type& value) {
        return value.size;
    }

    // Operator Monoid (Affine Composition)
    // f(x) = a1*x + b1, g(x) = a2*x + b2
    // f(g(x)) = a1*(a2*x + b2) + b1 = (a1*a2)*x + (a1*b2 + b1)
    static constexpr operator_type op_id() {
        return {T(1), T(0)};
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return {f.first * g.first, f.first * g.second + f.second};
    }

    // Mapping
    // \sum (a*x_i + b) = a * \sum x_i + b * size
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        return {f.first * x.sum + f.second * T(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