Range XOR Range Sum
(acted_monoid/range_xor_range_sum.hpp)
- View this file on GitHub
- Last update: 2026-07-21 20:17:47+09:00
- Include:
#include "acted_monoid/range_xor_range_sum.hpp"
Overview
An Acted Monoid representing Range Bitwise XOR operations and Range Sum queries.
Mathematical Mechanism
Because the XOR operation acts bit-by-bit, it does not distribute directly over addition ($C \oplus (A + B) \neq (C \oplus A) + (C \oplus B)$). To compute the new sum of a range after XORing by a value $f$, the segment tree node must independently track how many times each bit is set in its range.
If the $i$-th bit of $f$ is set, the new number of set bits at position $i$ within the segment becomes size - old_bit_count. The total sum is then re-evaluated based on the new bit counts.
Template Parameters
-
T: The underlying numerical type (e.g.,long long). -
BITS: The maximum bit length to track. Defaults to30(sufficient for standard $10^9$ integers). If operating onlong longvalues up to $10^{18}$, you should explicitly set this to60.
Initialization
When initializing a Lazy Segment Tree, you must use the make(val) helper function so that the leaf nodes correctly initialize their internal bit count arrays and size.
Example
#include "ds/segtree/lazy_segtree.hpp"
#include "acted_monoid/range_xor_range_sum.hpp"
#include <iostream>
#include <vector>
using AM = m1une::acted_monoid::RangeXorRangeSum<long long, 30>;
int main() {
std::vector<long long> A = {1, 2, 3, 4, 5};
int N = A.size();
std::vector<AM::value_type> init_nodes(N);
for (int i = 0; i < N; ++i) {
init_nodes[i] = AM::make(A[i]);
}
m1une::ds::LazySegtree<AM> seg(init_nodes);
// Get the sum of range [0, 4) -> 1 + 2 + 3 + 4 = 10
std::cout << "Initial Sum: " << seg.prod(0, 4).sum << "\n";
// XOR the range [0, 4) with 7
// 1^7 = 6, 2^7 = 5, 3^7 = 4, 4^7 = 3
// Array becomes: {6, 5, 4, 3, 5}
seg.apply(0, 4, 7);
// Get the new sum of range [0, 4) -> 6 + 5 + 4 + 3 = 18
std::cout << "Updated Sum: " << seg.prod(0, 4).sum << "\n";
return 0;
}
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
Code
#ifndef M1UNE_ACTED_MONOID_RANGE_XOR_RANGE_SUM_HPP
#define M1UNE_ACTED_MONOID_RANGE_XOR_RANGE_SUM_HPP 1
#include <array>
namespace m1une {
namespace acted_monoid {
template <typename T, int BITS = 30>
struct RangeXorRangeSumNode {
T sum;
std::array<int, BITS> bit_count;
long long size;
};
// Acted Monoid for Range XOR updates and Range Sum queries.
// BITS defines the maximum bit length (default 30 for standard integers, use 60 for long long).
template <typename T, int BITS = 30>
struct RangeXorRangeSum {
using value_type = RangeXorRangeSumNode<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 - x.bit_count[i];
}
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_XOR_RANGE_SUM_HPP#line 1 "acted_monoid/range_xor_range_sum.hpp"
#include <array>
namespace m1une {
namespace acted_monoid {
template <typename T, int BITS = 30>
struct RangeXorRangeSumNode {
T sum;
std::array<int, BITS> bit_count;
long long size;
};
// Acted Monoid for Range XOR updates and Range Sum queries.
// BITS defines the maximum bit length (default 30 for standard integers, use 60 for long long).
template <typename T, int BITS = 30>
struct RangeXorRangeSum {
using value_type = RangeXorRangeSumNode<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 - x.bit_count[i];
}
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