Range OR Range Sum
(acted_monoid/range_or_range_sum.hpp)

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

Overview

An Acted Monoid representing Range Bitwise OR operations and Range Sum queries.

Mathematical Mechanism

Because Bitwise OR does not distribute directly over addition, the node must track how many times each individual bit is set within its range. When a Range OR is applied with a value $f$, any bit set to 1 in $f$ forces that specific bit to become 1 for every element in the segment. Its bit count immediately becomes equal to size.

Template Parameters

• T: The underlying numerical type.
• BITS: Max bit length (default 30). Set to 60 for long long bounds.

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_OR_RANGE_SUM_HPP
#define M1UNE_ACTED_MONOID_RANGE_OR_RANGE_SUM_HPP 1

#include <array>

namespace m1une {
namespace acted_monoid {

template <typename T, int BITS = 30>
struct RangeOrRangeSumNode {
    T sum;
    std::array<int, BITS> bit_count;
    long long size;
};

// Acted Monoid for Range OR updates and Range Sum queries.
template <typename T, int BITS = 30>
struct RangeOrRangeSum {
    using value_type = RangeOrRangeSumNode<T, BITS>;
    using operator_type = T;
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = true;

    static constexpr value_type id() {
        value_type res;
        res.sum = T(0);
        res.bit_count.fill(0);
        res.size = 0;
        return res;
    }

    static constexpr value_type op(const value_type& a, const value_type& b) {
        value_type res;
        res.sum = a.sum + b.sum;
        res.size = a.size + b.size;
        for (int i = 0; i < BITS; ++i) {
            res.bit_count[i] = a.bit_count[i] + b.bit_count[i];
        }
        return res;
    }

    static constexpr operator_type op_id() {
        return T(0);
    }

    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f | g;
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (f == T(0) || x.size == 0) return x;
        value_type res = x;
        res.sum = T(0);
        for (int i = 0; i < BITS; ++i) {
            if ((f >> i) & 1) {
                res.bit_count[i] = x.size;  // OR forces the bit to be 1 for all elements
            }
            res.sum += static_cast<T>(res.bit_count[i]) * (T(1) << i);
        }
        return res;
    }

    static constexpr value_type make(const T& val) {
        value_type res;
        res.sum = val;
        res.size = 1;
        for (int i = 0; i < BITS; ++i) {
            res.bit_count[i] = ((val >> i) & 1) ? 1 : 0;
        }
        return res;
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_OR_RANGE_SUM_HPP

#line 1 "acted_monoid/range_or_range_sum.hpp"



#include <array>

namespace m1une {
namespace acted_monoid {

template <typename T, int BITS = 30>
struct RangeOrRangeSumNode {
    T sum;
    std::array<int, BITS> bit_count;
    long long size;
};

// Acted Monoid for Range OR updates and Range Sum queries.
template <typename T, int BITS = 30>
struct RangeOrRangeSum {
    using value_type = RangeOrRangeSumNode<T, BITS>;
    using operator_type = T;
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = true;

    static constexpr value_type id() {
        value_type res;
        res.sum = T(0);
        res.bit_count.fill(0);
        res.size = 0;
        return res;
    }

    static constexpr value_type op(const value_type& a, const value_type& b) {
        value_type res;
        res.sum = a.sum + b.sum;
        res.size = a.size + b.size;
        for (int i = 0; i < BITS; ++i) {
            res.bit_count[i] = a.bit_count[i] + b.bit_count[i];
        }
        return res;
    }

    static constexpr operator_type op_id() {
        return T(0);
    }

    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f | g;
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (f == T(0) || x.size == 0) return x;
        value_type res = x;
        res.sum = T(0);
        for (int i = 0; i < BITS; ++i) {
            if ((f >> i) & 1) {
                res.bit_count[i] = x.size;  // OR forces the bit to be 1 for all elements
            }
            res.sum += static_cast<T>(res.bit_count[i]) * (T(1) << i);
        }
        return res;
    }

    static constexpr value_type make(const T& val) {
        value_type res;
        res.sum = val;
        res.size = 1;
        for (int i = 0; i < BITS; ++i) {
            res.bit_count[i] = ((val >> i) & 1) ? 1 : 0;
        }
        return res;
    }
};

}  // namespace acted_monoid
}  // namespace m1une

Back to top page