Range Update Range Product
(acted_monoid/range_update_range_product.hpp)

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

Overview

m1une::acted_monoid::RangeUpdateRangeProduct<Monoid> adapts any monoid for range assignment and range product queries. It works for noncommutative monoids: the product keeps the original left-to-right order defined by Monoid::op.

Assigning value to a segment of length $k$ changes its aggregate to $value^k$. The adapter computes this power with binary exponentiation.

Requirements and behavior

Monoid must satisfy m1une::monoid::IsMonoid. In particular, it provides:

using value_type = ...;
static value_type id();
static value_type op(const value_type&, const value_type&);

The operator type is std::optional<Monoid::value_type>. std::nullopt means no assignment, and a present value overwrites every element of the segment. When lazy assignments are composed, the newer present assignment wins.

The aggregate node stores both product and size. Initialize a lazy segment tree from std::vector<Monoid::value_type> so that its adapting constructor calls make(value), or call make(value) yourself. The size-only LazySegtree<AM>(n) constructor creates identity nodes of length zero and is not suitable until every leaf has been replaced with a node returned by make.

Interface

For using AM = m1une::acted_monoid::RangeUpdateRangeProduct<Monoid>;:

Member	Signature	Meaning	Complexity
Base value	`using base_type = typename Monoid::value_type;`	One array element.	–
Aggregate	`using value_type = RangeUpdateRangeProductNode<Monoid>;`	Stores `base_type product` and `long long size`.	–
Lazy operator	`using operator_type = std::optional<base_type>;`	A range assignment, or no operation.	–
Identity	`static constexpr value_type id();`	Empty product with size zero.	One `Monoid::id()` call.
Product	`static constexpr value_type op(const value_type& a, const value_type& b);`	Concatenates `a` followed by `b`.	One `Monoid::op()` call.
Operator identity	`static constexpr operator_type op_id();`	Returns `std::nullopt`.	$O(1)$
Operator composition	`static constexpr operator_type op_comp(const operator_type& f, const operator_type& g);`	Returns `f` when present, otherwise `g`; `f` is newer.	$O(1)$ plus copying one operator.
Apply assignment	`static constexpr value_type mapping(const operator_type& f, const value_type& x);`	Replaces `x.product` by the assigned value to the power `x.size`.	$O(\log x.size)$ monoid operations for an assignment; otherwise one node copy.
Make leaf	`static constexpr value_type make(const base_type& value);`	Returns `{value, 1}`.	One value copy.

With m1une::ds::LazySegtree<AM> on $N$ elements, construction and range product take $O(N)$ and $O(\log N)$ monoid operations respectively. A range assignment takes $O(\log^2 N)$ monoid operations in the worst case because up to $O(\log N)$ segment-tree nodes each compute a power. Memory use is $O(N)$.

Example

#include "acted_monoid/range_update_range_product.hpp"
#include "ds/segtree/lazy_segtree.hpp"

#include <iostream>
#include <string>
#include <vector>

struct Concat {
    using value_type = std::string;

    static value_type id() {
        return "";
    }

    static value_type op(const value_type& left, const value_type& right) {
        return left + right;
    }
};

int main() {
    using AM = m1une::acted_monoid::RangeUpdateRangeProduct<Concat>;

    std::vector<std::string> values = {"a", "b", "c", "d"};
    m1une::ds::LazySegtree<AM> seg(values);

    seg.apply(1, 3, std::string("x"));
    std::cout << seg.prod(0, 4).product << '\n';  // axxd
}

Depends on

Verified with

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_UPDATE_RANGE_PRODUCT_HPP
#define M1UNE_ACTED_MONOID_RANGE_UPDATE_RANGE_PRODUCT_HPP 1

#include <optional>

#include "../monoid/concept.hpp"
#include "../monoid/power.hpp"

namespace m1une {
namespace acted_monoid {

template <m1une::monoid::IsMonoid Monoid>
struct RangeUpdateRangeProductNode {
    using base_type = typename Monoid::value_type;

    base_type product;
    long long size;
};

// Range assignment and range product for an arbitrary, possibly
// noncommutative, monoid.
template <m1une::monoid::IsMonoid Monoid>
struct RangeUpdateRangeProduct {
    using base_type = typename Monoid::value_type;
    using value_type = RangeUpdateRangeProductNode<Monoid>;
    using operator_type = std::optional<base_type>;
    static constexpr bool commutative = [] {
        if constexpr (requires { Monoid::commutative; }) {
            return bool(Monoid::commutative);
        } else {
            return false;
        }
    }();
    static constexpr bool operator_commutative = false;

    static constexpr value_type id() {
        return {Monoid::id(), 0};
    }

    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {Monoid::op(a.product, b.product), a.size + b.size};
    }

    static constexpr operator_type op_id() {
        return std::nullopt;
    }

    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f.has_value() ? f : g;
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (!f.has_value() || x.size == 0) return x;
        return {m1une::monoid::power<Monoid>(f.value(), x.size), x.size};
    }

    static constexpr value_type make(const base_type& value) {
        return {value, 1};
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_UPDATE_RANGE_PRODUCT_HPP

#line 1 "acted_monoid/range_update_range_product.hpp"



#include <optional>

#line 1 "monoid/concept.hpp"



#include <concepts>

namespace m1une {
namespace monoid {

// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
    // 1. Must define `value_type`
    typename M::value_type;

    // 2. Must have a static method `id()` returning `value_type`
    { M::id() } -> std::same_as<typename M::value_type>;

    // 3. Must have a static method `op(a, b)` returning `value_type`
    { M::op(a, b) } -> std::same_as<typename M::value_type>;
};

// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
    { M::inv(a) } -> std::same_as<typename M::value_type>;
};

// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;

}  // namespace monoid
}  // namespace m1une


#line 1 "monoid/power.hpp"



#line 5 "monoid/power.hpp"

namespace m1une {
namespace monoid {

// Computes a^n (a * a * ... * a, n times) for an element 'a' in Monoid 'M'.
// Uses binary exponentiation to achieve O(log n) time complexity.
// The template parameter 'M' is constrained by the 'IsMonoid' concept.
template <IsMonoid M>
constexpr typename M::value_type power(typename M::value_type a, long long n) {
    typename M::value_type res = M::id();
    while (n > 0) {
        if (n & 1) {
            res = M::op(res, a);
        }
        a = M::op(a, a);
        n >>= 1;
    }
    return res;
}

}  // namespace monoid
}  // namespace m1une


#line 8 "acted_monoid/range_update_range_product.hpp"

namespace m1une {
namespace acted_monoid {

template <m1une::monoid::IsMonoid Monoid>
struct RangeUpdateRangeProductNode {
    using base_type = typename Monoid::value_type;

    base_type product;
    long long size;
};

// Range assignment and range product for an arbitrary, possibly
// noncommutative, monoid.
template <m1une::monoid::IsMonoid Monoid>
struct RangeUpdateRangeProduct {
    using base_type = typename Monoid::value_type;
    using value_type = RangeUpdateRangeProductNode<Monoid>;
    using operator_type = std::optional<base_type>;
    static constexpr bool commutative = [] {
        if constexpr (requires { Monoid::commutative; }) {
            return bool(Monoid::commutative);
        } else {
            return false;
        }
    }();
    static constexpr bool operator_commutative = false;

    static constexpr value_type id() {
        return {Monoid::id(), 0};
    }

    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {Monoid::op(a.product, b.product), a.size + b.size};
    }

    static constexpr operator_type op_id() {
        return std::nullopt;
    }

    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f.has_value() ? f : g;
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (!f.has_value() || x.size == 0) return x;
        return {m1une::monoid::power<Monoid>(f.value(), x.size), x.size};
    }

    static constexpr value_type make(const base_type& value) {
        return {value, 1};
    }
};

}  // namespace acted_monoid
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Range Update Range Product
(acted_monoid/range_update_range_product.hpp)

Overview

Requirements and behavior

Interface

Example

Depends on

Verified with

Code

Range Update Range Product (acted_monoid/range_update_range_product.hpp)

Overview

Requirements and behavior

Interface

Example

Depends on

Verified with

Code

Range Update Range Product
(acted_monoid/range_update_range_product.hpp)