algebra/monoid/monoid_affine.hpp

• View this file on GitHub
• Last update: 2026-04-11 00:41:57+09:00
• Include: #include "algebra/monoid/monoid_affine.hpp"

Required by

• algebra/acted_monoid/acted_monoid_plus_affine.hpp

Verified with

• segment_tree/test/lazy_segment_tree_sum_affine.test.cpp

Code

#pragma once

template <class T> struct Affine {
    T a;
    T b;
    friend std::ostream& operator<<(std::ostream& os, const Affine& f) {
        return os << f.a << ", " << f.b;
    }
};

template <class T> struct MonoidAffine {
    using value_type = Affine<T>;
    static constexpr value_type operation(const value_type& f,
                                          const value_type& g) noexcept {
        // f(x) := ax + b, g(x) := cx + d
        // g(f(x)) = c(ax + b) + d = cax + cb + d
        return {g.a * f.a, g.a * f.b + g.b};
    }
    static constexpr value_type identity() noexcept { return {T(1), T(0)}; }
};

#line 2 "algebra/monoid/monoid_affine.hpp"

template <class T> struct Affine {
    T a;
    T b;
    friend std::ostream& operator<<(std::ostream& os, const Affine& f) {
        return os << f.a << ", " << f.b;
    }
};

template <class T> struct MonoidAffine {
    using value_type = Affine<T>;
    static constexpr value_type operation(const value_type& f,
                                          const value_type& g) noexcept {
        // f(x) := ax + b, g(x) := cx + d
        // g(f(x)) = c(ax + b) + d = cax + cb + d
        return {g.a * f.a, g.a * f.b + g.b};
    }
    static constexpr value_type identity() noexcept { return {T(1), T(0)}; }
};

Back to top page