Update Monoid
(monoid/update.hpp)

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

Overview

A monoid for range updates/assignments. It uses std::optional<T> to safely represent whether an assignment operation exists or not (the identity element is std::nullopt).

When two operations are composed, the newer operation (on the left, when applied) completely overwrites the older operation (on the right), unless the newer operation is empty.

Template Parameters

• T: The underlying data type being assigned.

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/persistent_dynamic_dual_segtree.test.cpp
• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_UPDATE_HPP
#define M1UNE_MONOID_UPDATE_HPP 1

#include <optional>

namespace m1une {
namespace monoid {

// Monoid for range updates/assignments.
// Uses std::optional to represent the presence of an assignment.
template <typename T>
struct Update {
    using value_type = std::optional<T>;
    static constexpr bool commutative = false;

    // The identity element represents "no operation".
    static constexpr value_type id() {
        return std::nullopt;
    }

    // Composes two updates. The newer operation 'a' overwrites the older 'b'.
    // If 'a' does not exist, it falls back to 'b'.
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return a.has_value() ? a : b;
    }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_UPDATE_HPP

#line 1 "monoid/update.hpp"



#include <optional>

namespace m1une {
namespace monoid {

// Monoid for range updates/assignments.
// Uses std::optional to represent the presence of an assignment.
template <typename T>
struct Update {
    using value_type = std::optional<T>;
    static constexpr bool commutative = false;

    // The identity element represents "no operation".
    static constexpr value_type id() {
        return std::nullopt;
    }

    // Composes two updates. The newer operation 'a' overwrites the older 'b'.
    // If 'a' does not exist, it falls back to 'b'.
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return a.has_value() ? a : b;
    }
};

}  // namespace monoid
}  // namespace m1une

Back to top page