Range Bitwise AND/OR Range Sum
(beats_acted_monoid/range_bitwise_and_or_range_sum.hpp)

View this file on GitHub
Last update: 2026-08-12 01:20:42+09:00
Include: #include "beats_acted_monoid/range_bitwise_and_or_range_sum.hpp"

Overview

m1une::beats_acted_monoid::RangeBitwiseAndOrRangeSum<T, BITS> is a Beats acted monoid for range bitwise AND and OR updates with range-sum queries.

Unlike the ordinary acted monoid that stores a count for every bit, this Beats version stores only the sum, aggregate bitwise AND, aggregate bitwise OR, and segment length. An update applies directly when every bit it changes is uniform throughout the node. If a changed bit is mixed, can_apply returns false and the Beats tree descends.

The lazy operator_type represents

f(x) = (x & and_mask) | or_mask;

Use make_and and make_or instead of constructing an operator directly.

Template requirements

T must be a non-boolean integral type. Values are nonnegative, occupy only the lowest BITS bits, and have range sums representable by T.
BITS defaults to 30 and must be between 1 and std::numeric_limits<T>::digits, inclusive.

value_type is RangeBitwiseAndOrRangeSumNode<T> and has these public members:

T sum;
T bitwise_and;
T bitwise_or;
long long length;

operator_type has public members T and_mask and T or_mask.

Interface and complexity

Every acted-monoid operation takes $O(1)$ time, independently of BITS.

Member	Description	Complexity
`static T bit_mask()`	Returns a mask with its lowest `BITS` bits set.	$O(1)$
`static value_type id()`	Returns the empty aggregate.	$O(1)$
`static value_type op(const value_type& x, const value_type& y)`	Concatenates two aggregates.	$O(1)$
`static operator_type op_id()`	Returns the identity update.	$O(1)$
`static operator_type op_comp(const operator_type& f, const operator_type& g)`	Returns $f \circ g$.	$O(1)$
`static bool can_apply(const operator_type& f, const value_type& x)`	Reports whether every changed bit is uniform in `x`.	$O(1)$
`static value_type mapping(const operator_type& f, const value_type& x)`	Applies an update after `can_apply` succeeds.	$O(1)$
`static value_type make(const T& value)`	Constructs a one-element aggregate.	$O(1)$
`static operator_type make_and(const T& mask)`	Constructs `x = x & mask`.	$O(1)$
`static operator_type make_or(const T& mask)`	Constructs `x = x \| mask`.	$O(1)$

With SegtreeBeats, an operation takes $O(\log N+D)$, where $D$ is the number of extra nodes visited because a changed bit is mixed. Read a query result from the returned node’s sum member.

Example

#include "beats_acted_monoid/range_bitwise_and_or_range_sum.hpp"
#include "ds/segtree/segtree_beats.hpp"

#include <iostream>
#include <vector>

using AM =
    m1une::beats_acted_monoid::RangeBitwiseAndOrRangeSum<long long, 30>;

int main() {
    std::vector<long long> values = {1, 2, 3, 4};
    m1une::ds::SegtreeBeats<AM> seg(values);

    seg.apply(0, 3, AM::make_or(4));
    seg.apply(1, 4, AM::make_and(6));

    std::cout << seg.prod(0, 4).sum << '\n';
}

Verified with

verify/beats_acted_monoid/range_bitwise_and_or_range_sum.test.cpp

Code

#ifndef M1UNE_BEATS_ACTED_MONOID_RANGE_BITWISE_AND_OR_RANGE_SUM_HPP
#define M1UNE_BEATS_ACTED_MONOID_RANGE_BITWISE_AND_OR_RANGE_SUM_HPP 1

#include <cassert>
#include <limits>
#include <type_traits>

namespace m1une {
namespace beats_acted_monoid {

template <typename T>
struct RangeBitwiseAndOrRangeSumNode {
    T sum;
    T bitwise_and;
    T bitwise_or;
    long long length;
};

// Beats acted monoid for range bitwise AND/OR updates and range sum queries.
template <typename T, int BITS = 30>
struct RangeBitwiseAndOrRangeSum {
    static_assert(
        std::is_integral_v<T> &&
        !std::is_same_v<std::remove_cv_t<T>, bool>
    );
    static_assert(0 < BITS && BITS <= std::numeric_limits<T>::digits);

    using value_type = RangeBitwiseAndOrRangeSumNode<T>;

    // Represents f(x) = (x & and_mask) | or_mask.
    struct operator_type {
        T and_mask;
        T or_mask;
    };

    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = false;

    static constexpr T bit_mask() {
        if constexpr (
            std::is_unsigned_v<T> &&
            BITS == std::numeric_limits<T>::digits
        ) {
            return ~T(0);
        } else {
            return
                (T(1) << (BITS - 1)) |
                ((T(1) << (BITS - 1)) - 1);
        }
    }

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

    static constexpr value_type op(
        const value_type& left,
        const value_type& right
    ) {
        return {
            left.sum + right.sum,
            left.bitwise_and & right.bitwise_and,
            left.bitwise_or | right.bitwise_or,
            left.length + right.length
        };
    }

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

    // Returns f(g(x)).
    static constexpr operator_type op_comp(
        const operator_type& f,
        const operator_type& g
    ) {
        return {
            (f.and_mask & g.and_mask) & bit_mask(),
            ((g.or_mask & f.and_mask) | f.or_mask) & bit_mask()
        };
    }

    static constexpr bool can_apply(
        const operator_type& f,
        const value_type& value
    ) {
        if (value.length == 0) return true;
        T changed = ((~f.and_mask) | f.or_mask) & bit_mask();
        T mixed = value.bitwise_and ^ value.bitwise_or;
        return (changed & mixed) == T(0);
    }

    static constexpr value_type mapping(
        const operator_type& f,
        const value_type& value
    ) {
        assert(can_apply(f, value));
        if (value.length == 0) return value;
        T changed = ((~f.and_mask) | f.or_mask) & bit_mask();
        T old_uniform = value.bitwise_and & changed;
        T new_uniform =
            ((old_uniform & f.and_mask) | f.or_mask) & changed;

        value_type result = value;
        result.sum +=
            (new_uniform - old_uniform) * T(value.length);
        result.bitwise_and =
            ((value.bitwise_and & f.and_mask) | f.or_mask) & bit_mask();
        result.bitwise_or =
            ((value.bitwise_or & f.and_mask) | f.or_mask) & bit_mask();
        return result;
    }

    static constexpr value_type make(const T& value) {
        assert((value & ~bit_mask()) == T(0));
        return {value, value, value, 1};
    }

    static constexpr operator_type make_and(const T& mask) {
        return {mask & bit_mask(), T(0)};
    }

    static constexpr operator_type make_or(const T& mask) {
        return {bit_mask(), mask & bit_mask()};
    }
};

}  // namespace beats_acted_monoid
}  // namespace m1une

#endif  // M1UNE_BEATS_ACTED_MONOID_RANGE_BITWISE_AND_OR_RANGE_SUM_HPP

#line 1 "beats_acted_monoid/range_bitwise_and_or_range_sum.hpp"



#include <cassert>
#include <limits>
#include <type_traits>

namespace m1une {
namespace beats_acted_monoid {

template <typename T>
struct RangeBitwiseAndOrRangeSumNode {
    T sum;
    T bitwise_and;
    T bitwise_or;
    long long length;
};

// Beats acted monoid for range bitwise AND/OR updates and range sum queries.
template <typename T, int BITS = 30>
struct RangeBitwiseAndOrRangeSum {
    static_assert(
        std::is_integral_v<T> &&
        !std::is_same_v<std::remove_cv_t<T>, bool>
    );
    static_assert(0 < BITS && BITS <= std::numeric_limits<T>::digits);

    using value_type = RangeBitwiseAndOrRangeSumNode<T>;

    // Represents f(x) = (x & and_mask) | or_mask.
    struct operator_type {
        T and_mask;
        T or_mask;
    };

    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = false;

    static constexpr T bit_mask() {
        if constexpr (
            std::is_unsigned_v<T> &&
            BITS == std::numeric_limits<T>::digits
        ) {
            return ~T(0);
        } else {
            return
                (T(1) << (BITS - 1)) |
                ((T(1) << (BITS - 1)) - 1);
        }
    }

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

    static constexpr value_type op(
        const value_type& left,
        const value_type& right
    ) {
        return {
            left.sum + right.sum,
            left.bitwise_and & right.bitwise_and,
            left.bitwise_or | right.bitwise_or,
            left.length + right.length
        };
    }

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

    // Returns f(g(x)).
    static constexpr operator_type op_comp(
        const operator_type& f,
        const operator_type& g
    ) {
        return {
            (f.and_mask & g.and_mask) & bit_mask(),
            ((g.or_mask & f.and_mask) | f.or_mask) & bit_mask()
        };
    }

    static constexpr bool can_apply(
        const operator_type& f,
        const value_type& value
    ) {
        if (value.length == 0) return true;
        T changed = ((~f.and_mask) | f.or_mask) & bit_mask();
        T mixed = value.bitwise_and ^ value.bitwise_or;
        return (changed & mixed) == T(0);
    }

    static constexpr value_type mapping(
        const operator_type& f,
        const value_type& value
    ) {
        assert(can_apply(f, value));
        if (value.length == 0) return value;
        T changed = ((~f.and_mask) | f.or_mask) & bit_mask();
        T old_uniform = value.bitwise_and & changed;
        T new_uniform =
            ((old_uniform & f.and_mask) | f.or_mask) & changed;

        value_type result = value;
        result.sum +=
            (new_uniform - old_uniform) * T(value.length);
        result.bitwise_and =
            ((value.bitwise_and & f.and_mask) | f.or_mask) & bit_mask();
        result.bitwise_or =
            ((value.bitwise_or & f.and_mask) | f.or_mask) & bit_mask();
        return result;
    }

    static constexpr value_type make(const T& value) {
        assert((value & ~bit_mask()) == T(0));
        return {value, value, value, 1};
    }

    static constexpr operator_type make_and(const T& mask) {
        return {mask & bit_mask(), T(0)};
    }

    static constexpr operator_type make_or(const T& mask) {
        return {bit_mask(), mask & bit_mask()};
    }
};

}  // namespace beats_acted_monoid
}  // namespace m1une

m1une's library

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

Range Bitwise AND/OR Range Sum
(beats_acted_monoid/range_bitwise_and_or_range_sum.hpp)

Overview

Template requirements

Interface and complexity

Example

Verified with

Code

Range Bitwise AND/OR Range Sum (beats_acted_monoid/range_bitwise_and_or_range_sum.hpp)

Overview

Template requirements

Interface and complexity

Example

Verified with

Code

Range Bitwise AND/OR Range Sum
(beats_acted_monoid/range_bitwise_and_or_range_sum.hpp)