Affine Monoid
(monoid/affine.hpp)

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

Overview

A monoid for composing affine transformations, expressed as $f(x) = ax + b$. The underlying value_type is std::pair<T, T>, where first represents $a$ (the multiplier) and second represents $b$ (the addend).

This is particularly useful when you have a sequence of operations like “multiply by $X$, then add $Y$” and you want to find the composite function of a range.

Initialization

You can create operations directly using pairs, or use the provided helper functions for clarity:

• Add $C$: make_add(C) -> {1, C}
• Multiply by $C$: make_mul(C) -> {C, 0}
• Assign $C$: make_assign(C) -> {0, C}

Example

#include "ds/segtree/segtree.hpp"
#include "monoid/affine.hpp"
#include <iostream>

using AffineM = m1une::monoid::Affine<long long>;

int main() {
    // Operations:
    // 0: f(x) = 2x + 3
    // 1: f(x) = 1x + 5 (Add 5)
    // 2: f(x) = 3x + 0 (Multiply by 3)

    std::vector<AffineM::value_type> ops = {
        {2, 3},
        AffineM::make_add(5),
        AffineM::make_mul(3)
    };

    m1une::ds::Segtree<AffineM> seg(ops);

    // Get the composite function for the range [0, 2)
    // f(x) = 1 * (2x + 3) + 5 = 2x + 8
    auto [a, b] = seg.prod(0, 2);
    std::cout << "f(x) = " << a << "x + " << b << "\n"; // Output: 2x + 8

    return 0;
}

Interface and Complexity

This is a stateless algebra tag. Generic data structures use its public value_type, id(), and op(a, b) members. If the type also provides helpers such as make(...) or inv(x), they are described above or in the documented properties.

Each static operation runs in the cost of the underlying operation shown in the properties. Scalar monoids are $O(1)$; monoids whose value_type stores several items, permutations, or matrices scale with that stored size.

Verified with

• verify/ds/segtree/dual_segtree.test.cpp
• verify/ds/segtree/dynamic_dual_segtree.test.cpp
• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_AFFINE_HPP
#define M1UNE_MONOID_AFFINE_HPP 1

#include <utility>

namespace m1une {
namespace monoid {

// Monoid for affine transformations f(x) = ax + b.
// Represented as a pair {a, b}.
template <typename T>
struct Affine {
    using value_type = std::pair<T, T>;
    static constexpr bool commutative = false;

    // The identity transformation is f(x) = 1*x + 0.
    static constexpr value_type id() {
        return {T(1), T(0)};
    }

    // Composes two affine transformations.
    // f(g(x)) where f = a, g = b.
    // a.first * (b.first * x + b.second) + a.second
    // = (a.first * b.first) * x + (a.first * b.second + a.second)
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {a.first * b.first, a.first * b.second + a.second};
    }

    // Helpers to create common affine transformations
    static constexpr value_type make_add(const T& b) {
        return {T(1), b};
    }
    static constexpr value_type make_mul(const T& a) {
        return {a, T(0)};
    }
    static constexpr value_type make_assign(const T& b) {
        return {T(0), b};
    }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_AFFINE_HPP

#line 1 "monoid/affine.hpp"



#include <utility>

namespace m1une {
namespace monoid {

// Monoid for affine transformations f(x) = ax + b.
// Represented as a pair {a, b}.
template <typename T>
struct Affine {
    using value_type = std::pair<T, T>;
    static constexpr bool commutative = false;

    // The identity transformation is f(x) = 1*x + 0.
    static constexpr value_type id() {
        return {T(1), T(0)};
    }

    // Composes two affine transformations.
    // f(g(x)) where f = a, g = b.
    // a.first * (b.first * x + b.second) + a.second
    // = (a.first * b.first) * x + (a.first * b.second + a.second)
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {a.first * b.first, a.first * b.second + a.second};
    }

    // Helpers to create common affine transformations
    static constexpr value_type make_add(const T& b) {
        return {T(1), b};
    }
    static constexpr value_type make_mul(const T& a) {
        return {a, T(0)};
    }
    static constexpr value_type make_assign(const T& b) {
        return {T(0), b};
    }
};

}  // namespace monoid
}  // namespace m1une

Back to top page