Max-Plus Matrix Monoid
(monoid/max_plus_matrix.hpp)

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

Overview

A monoid for range matrix multiplication over the Max-Plus semiring. In this algebra, the standard addition operation is replaced by std::max, and the standard multiplication operation is replaced by regular addition +.

This is highly effective for solving Dynamic DP problems (where state transitions involve taking the maximum of sums) or finding longest paths over dynamic edge weights on a Segment Tree.

Example

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

using MaxMat = m1une::monoid::MaxPlusMatrix<long long, 2>;

int main() {
    int N = 3;
    std::vector<MaxMat::value_type> init_data(N);

    for (int i = 0; i < N; ++i) {
        auto mat = MaxMat::make_inf();
        mat[0][0] = 5;
        mat[0][1] = 2;
        mat[1][0] = 3;
        mat[1][1] = 0;
        init_data[i] = mat;
    }

    m1une::ds::Segtree<MaxMat> seg(init_data);

    auto res = seg.prod(0, N);

    std::cout << "Max Cost 0 -> 0: " << res[0][0] << "\n";
    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/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_MAX_PLUS_MATRIX_HPP
#define M1UNE_MONOID_MAX_PLUS_MATRIX_HPP 1

#include <algorithm>
#include <array>
#include <limits>

namespace m1une {
namespace monoid {

// Monoid for fixed-size square matrix multiplication over the Max-Plus semiring.
// Useful for Dynamic DP (Maximization) and Longest Path problems.
template <typename T, int N, T MinInf = std::numeric_limits<T>::lowest() / 2>
struct MaxPlusMatrix {
    using value_type = std::array<std::array<T, N>, N>;
    static constexpr bool commutative = false;

    // The identity matrix for max-plus algebra.
    // Diagonal elements are 0 (identity for addition).
    // Off-diagonal elements are MinInf (identity for max).
    static constexpr value_type id() {
        value_type res{};
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                res[i][j] = (i == j) ? T(0) : MinInf;
            }
        }
        return res;
    }

    // Multiplies two max-plus matrices: c_{i, j} = max_k (a_{i, k} + b_{k, j})
    static constexpr value_type op(const value_type& a, const value_type& b) {
        value_type res{};
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                res[i][j] = MinInf;
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int k = 0; k < N; ++k) {
                if (a[i][k] == MinInf) continue;
                for (int j = 0; j < N; ++j) {
                    if (b[k][j] == MinInf) continue;
                    res[i][j] = std::max(res[i][j], a[i][k] + b[k][j]);
                }
            }
        }
        return res;
    }

    // Helper to securely create a matrix initialized with MinInf.
    static constexpr value_type make_inf() {
        value_type res{};
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                res[i][j] = MinInf;
            }
        }
        return res;
    }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_MAX_PLUS_MATRIX_HPP

#line 1 "monoid/max_plus_matrix.hpp"



#include <algorithm>
#include <array>
#include <limits>

namespace m1une {
namespace monoid {

// Monoid for fixed-size square matrix multiplication over the Max-Plus semiring.
// Useful for Dynamic DP (Maximization) and Longest Path problems.
template <typename T, int N, T MinInf = std::numeric_limits<T>::lowest() / 2>
struct MaxPlusMatrix {
    using value_type = std::array<std::array<T, N>, N>;
    static constexpr bool commutative = false;

    // The identity matrix for max-plus algebra.
    // Diagonal elements are 0 (identity for addition).
    // Off-diagonal elements are MinInf (identity for max).
    static constexpr value_type id() {
        value_type res{};
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                res[i][j] = (i == j) ? T(0) : MinInf;
            }
        }
        return res;
    }

    // Multiplies two max-plus matrices: c_{i, j} = max_k (a_{i, k} + b_{k, j})
    static constexpr value_type op(const value_type& a, const value_type& b) {
        value_type res{};
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                res[i][j] = MinInf;
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int k = 0; k < N; ++k) {
                if (a[i][k] == MinInf) continue;
                for (int j = 0; j < N; ++j) {
                    if (b[k][j] == MinInf) continue;
                    res[i][j] = std::max(res[i][j], a[i][k] + b[k][j]);
                }
            }
        }
        return res;
    }

    // Helper to securely create a matrix initialized with MinInf.
    static constexpr value_type make_inf() {
        value_type res{};
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                res[i][j] = MinInf;
            }
        }
        return res;
    }
};

}  // namespace monoid
}  // namespace m1une

Back to top page