Range Affine Range Sum of Squares
(acted_monoid/range_affine_range_sum_of_squares.hpp)

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

Overview

An Acted Monoid representing Range Affine Transformations ($f(x) = ax + b$) and Range Sum of Squares queries. This is an incredibly powerful structure for calculating expected values, variances, or quadratic constraints over dynamic arrays in $O(\log N)$ time.

Mathematical Mechanism

When an affine transformation $f(x) = ax + b$ is applied to a range, the new sum of squares is expanded algebraically: \(\sum (ax_i + b)^2 = a^2 \left(\sum x_i^2\right) + 2ab \left(\sum x_i\right) + b^2 \cdot \text{size}\)

To support this $O(1)$ mapping operation, the node state (value_type) tracks three properties of the segment: the sum of squares (sum_sq), the standard sum (sum), and the size.

Template Parameters

• T: The underlying numerical type. This is often used with a modular arithmetic struct (e.g., Modint) to prevent overflow, but standard long long works if numbers are small.

Operator Details

The operator_type is an std::pair<T, T> representing {a, b} in $f(x) = ax + b$. This allows you to perform multiple types of range operations seamlessly:

• Range Add $C$: Use {1, C}
• Range Multiply $C$: Use {C, 0}
• Range Assign/Overwrite $C$: Use {0, C} (the $a=0$ coefficient completely zeroes out the old sum, effectively replacing the entire segment).

Example

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

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

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

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

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

    // Initial sum of squares for [0, 3): 1^2 + 2^2 + 3^2 = 14
    std::cout << "Initial Sum_Sq: " << seg.prod(0, 3).sum_sq << "\n"; // Output: 14

    // Apply affine function: f(x) = 2x + 1 to range [0, 2)
    // 1 -> 2(1)+1 = 3
    // 2 -> 2(2)+1 = 5
    // Array becomes: {3, 5, 3}
    seg.apply(0, 2, {2, 1});

    // New sum of squares for [0, 3): 3^2 + 5^2 + 3^2 = 9 + 25 + 9 = 43
    std::cout << "Updated Sum_Sq: " << seg.prod(0, 3).sum_sq << "\n"; // Output: 43

    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_AFFINE_RANGE_SUM_OF_SQUARES_HPP
#define M1UNE_ACTED_MONOID_RANGE_AFFINE_RANGE_SUM_OF_SQUARES_HPP 1

#include <utility>

namespace m1une {
namespace acted_monoid {

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

// Designed to work with standard scalars or Modint types
template <typename T>
struct RangeAffineRangeSumOfSquares {
    using value_type = RangeAffineRangeSumOfSquaresNode<T>;
    using operator_type = std::pair<T, T>;  // {a, b} for f(x) = a*x + b
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = false;

    // Value Monoid (Sum of Squares, Sum, Size)
    static constexpr value_type id() {
        return {T(0), T(0), 0};
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {a.sum_sq + b.sum_sq, a.sum + b.sum, a.size + b.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)^2 = a^2 \sum x_i^2 + 2ab \sum x_i + b^2 * size
    // \sum (a*x_i + b)   = a \sum x_i + b * size
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (x.size == 0) return x;
        T a = f.first;
        T b = f.second;
        T sz = static_cast<T>(x.size);

        return {a * a * x.sum_sq + T(2) * a * b * x.sum + b * b * sz, a * x.sum + b * sz, x.size};
    }

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

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_AFFINE_RANGE_SUM_OF_SQUARES_HPP

#line 1 "acted_monoid/range_affine_range_sum_of_squares.hpp"



#include <utility>

namespace m1une {
namespace acted_monoid {

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

// Designed to work with standard scalars or Modint types
template <typename T>
struct RangeAffineRangeSumOfSquares {
    using value_type = RangeAffineRangeSumOfSquaresNode<T>;
    using operator_type = std::pair<T, T>;  // {a, b} for f(x) = a*x + b
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = false;

    // Value Monoid (Sum of Squares, Sum, Size)
    static constexpr value_type id() {
        return {T(0), T(0), 0};
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {a.sum_sq + b.sum_sq, a.sum + b.sum, a.size + b.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)^2 = a^2 \sum x_i^2 + 2ab \sum x_i + b^2 * size
    // \sum (a*x_i + b)   = a \sum x_i + b * size
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (x.size == 0) return x;
        T a = f.first;
        T b = f.second;
        T sz = static_cast<T>(x.size);

        return {a * a * x.sum_sq + T(2) * a * b * x.sum + b * b * sz, a * x.sum + b * sz, x.size};
    }

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

}  // namespace acted_monoid
}  // namespace m1une

Back to top page