Range Update Range Max Subarray
(acted_monoid/range_update_range_max_subarray.hpp)

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

Overview

An Acted Monoid for answering Maximum Contiguous Subarray Sum queries subject to Range Assignment (Set/Update) operations.

It maintains the total sum, prefix max, suffix max, and maximum subarray sum for each segment tree node. This represents a classic competitive programming pattern (e.g., CSES “Hotel Queries” variations or AtCoder Library practice).

Usage Notes

• operator_type uses std::optional<T>, where std::nullopt represents no operation.
• By default, it allows picking an empty subarray (the minimum possible answer is 0).

Example

using AM = m1une::acted_monoid::RangeUpdateRangeMaxSubarray<long long>;
// seg.prod(l, r).max_sub will give the maximum subarray sum in range [l, r)
// seg.apply(l, r, 5) will set all elements in [l, r) to 5.

Interface and Complexity

This is a stateless acted-monoid tag. Lazy data structures use its public value_type, operator_type, id(), op(a, b), op_id(), op_comp(f, g), and mapping(f, x) members. Helpers such as make(...), shifted mappings, or reversal-aware mappings are described above when the header provides them.

The static operations are $O(1)$ for the scalar metadata stored by these range acted monoids, aside from the cost of the underlying arithmetic type.

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_UPDATE_RANGE_MAX_SUBARRAY_HPP
#define M1UNE_ACTED_MONOID_RANGE_UPDATE_RANGE_MAX_SUBARRAY_HPP 1

#include <algorithm>
#include <optional>

namespace m1une {
namespace acted_monoid {

template <typename T>
struct RangeUpdateRangeMaxSubarrayNode {
    T sum, pref, suff, max_sub;
    long long size;
};

// Acted Monoid for Range Assignment (Update) and Max Contiguous Subarray Sum.
// Note: This implementation assumes empty subarrays are allowed (max sum is at least 0).
template <typename T>
struct RangeUpdateRangeMaxSubarray {
    using value_type = RangeUpdateRangeMaxSubarrayNode<T>;
    using operator_type = std::optional<T>;
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = false;

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

    static constexpr value_type op(const value_type& a, const value_type& b) {
        if (a.size == 0) return b;
        if (b.size == 0) return a;
        value_type res;
        res.sum = a.sum + b.sum;
        res.pref = std::max(a.pref, a.sum + b.pref);
        res.suff = std::max(b.suff, b.sum + a.suff);
        res.max_sub = std::max({a.max_sub, b.max_sub, a.suff + b.pref});
        res.size = a.size + b.size;
        return res;
    }

    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 ? f : g;  // left-biased because new updates override old ones
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (!f || x.size == 0) return x;
        value_type res;
        res.sum = (*f) * x.size;
        T max_val = std::max(T(0), res.sum);
        // If empty subarrays are NOT allowed, change to: T max_val = (*f) > 0 ? res.sum : (*f);
        res.pref = res.suff = res.max_sub = max_val;
        res.size = x.size;
        return res;
    }

    static constexpr value_type make(const T& val) {
        T max_val = std::max(T(0), val);
        return {val, max_val, max_val, max_val, 1};
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_UPDATE_RANGE_MAX_SUBARRAY_HPP

#line 1 "acted_monoid/range_update_range_max_subarray.hpp"



#include <algorithm>
#include <optional>

namespace m1une {
namespace acted_monoid {

template <typename T>
struct RangeUpdateRangeMaxSubarrayNode {
    T sum, pref, suff, max_sub;
    long long size;
};

// Acted Monoid for Range Assignment (Update) and Max Contiguous Subarray Sum.
// Note: This implementation assumes empty subarrays are allowed (max sum is at least 0).
template <typename T>
struct RangeUpdateRangeMaxSubarray {
    using value_type = RangeUpdateRangeMaxSubarrayNode<T>;
    using operator_type = std::optional<T>;
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = false;

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

    static constexpr value_type op(const value_type& a, const value_type& b) {
        if (a.size == 0) return b;
        if (b.size == 0) return a;
        value_type res;
        res.sum = a.sum + b.sum;
        res.pref = std::max(a.pref, a.sum + b.pref);
        res.suff = std::max(b.suff, b.sum + a.suff);
        res.max_sub = std::max({a.max_sub, b.max_sub, a.suff + b.pref});
        res.size = a.size + b.size;
        return res;
    }

    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 ? f : g;  // left-biased because new updates override old ones
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (!f || x.size == 0) return x;
        value_type res;
        res.sum = (*f) * x.size;
        T max_val = std::max(T(0), res.sum);
        // If empty subarrays are NOT allowed, change to: T max_val = (*f) > 0 ? res.sum : (*f);
        res.pref = res.suff = res.max_sub = max_val;
        res.size = x.size;
        return res;
    }

    static constexpr value_type make(const T& val) {
        T max_val = std::max(T(0), val);
        return {val, max_val, max_val, max_val, 1};
    }
};

}  // namespace acted_monoid
}  // namespace m1une

Back to top page