Range Bitwise AND/OR/XOR Range Sum
(acted_monoid/range_bitwise_and_or_xor_range_sum.hpp)

View this file on GitHub
Last update: 2026-08-12 00:05:48+09:00
Include: #include "acted_monoid/range_bitwise_and_or_xor_range_sum.hpp"

Overview

RangeBitwiseAndOrXorRangeSum<T, BITS> is an acted monoid for range bitwise AND, OR, and XOR updates and range sum queries. It is intended for lazy data structures such as LazySegtree.

Each value node stores the segment sum, size, and set-bit count at every tracked bit. A lazy operator represents

\[f(x) = (x \mathbin{\&} a) \mathbin{\hat{}} b.\]

This form represents AND, OR, XOR, and every composition of those operations. The order of lazy operators matters.

value_type has members T sum, std::array<long long, BITS> bit_count, and long long size. operator_type has members T and_mask and T xor_mask. Prefer the three update factories below instead of constructing an operator directly.

Template Parameters

T: A non-boolean integral type used for values, masks, and sums. Values must be nonnegative and fit in the lowest BITS bits. The sum must fit in T.
BITS: Number of low bits to track. It defaults to 30 and must not exceed std::numeric_limits<T>::digits. For values below $2^{60}$, use RangeBitwiseAndOrXorRangeSum<long long, 60>.

Interface and Complexity

Let $B = \mathtt{BITS}$.

Member	Description	Complexity
`static constexpr value_type id()`	Returns the empty value-monoid identity.	$O(B)$
`static constexpr value_type op(const value_type& x, const value_type& y)`	Concatenates two aggregates.	$O(B)$
`static constexpr T bit_mask()`	Returns a mask whose lowest `BITS` bits are set.	$O(1)$
`static constexpr operator_type op_id()`	Returns the identity lazy operator.	$O(1)$
`static constexpr operator_type op_comp(const operator_type& f, const operator_type& g)`	Returns the composition $f \circ g$.	$O(1)$
`static constexpr value_type mapping(const operator_type& f, const value_type& x)`	Applies `f` to an aggregate.	$O(B)$
`static constexpr value_type make(const T& value)`	Constructs a one-element aggregate.	$O(B)$
`static constexpr operator_type make_and(const T& mask)`	Constructs the update $x \gets x \mathbin{\&} \mathtt{mask}$.	$O(1)$
`static constexpr operator_type make_or(const T& mask)`	Constructs the update $x \gets x \mathbin{	} \mathtt{mask}$.	$O(1)$
`static constexpr operator_type make_xor(const T& mask)`	Constructs the update $x \gets x \mathbin{\hat{}} \mathtt{mask}$.	$O(1)$

With LazySegtree, construction takes $O(NB)$, a range update takes $O(B \log N)$, and a range-sum query takes $O(B \log N)$. Read the answer from the returned node’s sum member.

Example

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

#include <iostream>
#include <vector>

using AM = m1une::acted_monoid::RangeBitwiseAndOrXorRangeSum<long long, 30>;

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

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

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

Verified with

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_BITWISE_AND_OR_XOR_RANGE_SUM_HPP
#define M1UNE_ACTED_MONOID_RANGE_BITWISE_AND_OR_XOR_RANGE_SUM_HPP 1

#include <array>
#include <limits>
#include <type_traits>

namespace m1une {
namespace acted_monoid {

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

// Acted monoid for range bitwise AND, OR, and XOR updates and range sum queries.
template <typename T, int BITS = 30>
struct RangeBitwiseAndOrXorRangeSum {
    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 = RangeBitwiseAndOrXorRangeSumNode<T, BITS>;

    // Represents f(x) = (x & and_mask) ^ xor_mask on the lowest BITS bits.
    struct operator_type {
        T and_mask;
        T xor_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() {
        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 {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, (g.xor_mask & f.and_mask) ^ f.xor_mask};
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        value_type res = x;
        res.sum = T(0);
        for (int i = 0; i < BITS; ++i) {
            long long count = ((f.and_mask >> i) & T(1)) ? x.bit_count[i] : 0;
            if ((f.xor_mask >> i) & T(1)) count = x.size - count;
            res.bit_count[i] = count;
            res.sum += static_cast<T>(count) * (T(1) << i);
        }
        return res;
    }

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

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

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

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

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_BITWISE_AND_OR_XOR_RANGE_SUM_HPP

#line 1 "acted_monoid/range_bitwise_and_or_xor_range_sum.hpp"



#include <array>
#include <limits>
#include <type_traits>

namespace m1une {
namespace acted_monoid {

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

// Acted monoid for range bitwise AND, OR, and XOR updates and range sum queries.
template <typename T, int BITS = 30>
struct RangeBitwiseAndOrXorRangeSum {
    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 = RangeBitwiseAndOrXorRangeSumNode<T, BITS>;

    // Represents f(x) = (x & and_mask) ^ xor_mask on the lowest BITS bits.
    struct operator_type {
        T and_mask;
        T xor_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() {
        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 {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, (g.xor_mask & f.and_mask) ^ f.xor_mask};
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        value_type res = x;
        res.sum = T(0);
        for (int i = 0; i < BITS; ++i) {
            long long count = ((f.and_mask >> i) & T(1)) ? x.bit_count[i] : 0;
            if ((f.xor_mask >> i) & T(1)) count = x.size - count;
            res.bit_count[i] = count;
            res.sum += static_cast<T>(count) * (T(1) << i);
        }
        return res;
    }

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

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

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

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

}  // namespace acted_monoid
}  // namespace m1une

m1une's library

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

Range Bitwise AND/OR/XOR Range Sum
(acted_monoid/range_bitwise_and_or_xor_range_sum.hpp)

Overview

Template Parameters

Interface and Complexity

Example

Verified with

Code

Range Bitwise AND/OR/XOR Range Sum (acted_monoid/range_bitwise_and_or_xor_range_sum.hpp)

Overview

Template Parameters

Interface and Complexity

Example

Verified with

Code

Range Bitwise AND/OR/XOR Range Sum
(acted_monoid/range_bitwise_and_or_xor_range_sum.hpp)