static_range_xor_basis.hpp¶
Prefix-persistent linear bases for maximum xor and membership in a static subarray, with O(B) queries and O(nB) preprocessing.
为静态数组区间建立线性基，回答子集异或最大值、可达性或秩等查询。
Implementation¶
#ifndef NOYA_STATIC_RANGE_XOR_BASIS_HPP
#define NOYA_STATIC_RANGE_XOR_BASIS_HPP 1
/// @complexity Time: O(nB) build and O(B) query for B-bit values.
/// Space: O(nB).
#include "noya/xor_basis.hpp"
#include <array>
#include <cassert>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Prefix-persistent linear bases for maximum xor and membership in a
/// static subarray, with O(B) queries and O(nB) preprocessing.
template <class UInt, int bits = std::numeric_limits<UInt>::digits>
struct static_range_xor_basis {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bits && bits <= std::numeric_limits<UInt>::digits);
struct entry {
UInt value = 0;
int position = -1;
};
int n = 0;
std::vector<std::array<entry, bits>> prefixes;
static_range_xor_basis() = default;
explicit static_range_xor_basis(const std::vector<UInt> &values) {
build(values);
}
void build(const std::vector<UInt> &values) {
n = int(values.size());
prefixes.assign(n + 1, {});
for (int position = 0; position < n; position++) {
prefixes[position + 1] = prefixes[position];
insert(prefixes[position + 1], values[position], position);
}
}
/// @brief Maximize seed xor x over subset x of values[left, right).
UInt max_xor(int left, int right, UInt seed = 0) const {
check_range(left, right);
const auto &basis = prefixes[right];
for (int bit = bits - 1; bit >= 0; bit--) {
if (basis[bit].position >= left &&
(seed ^ basis[bit].value) > seed) {
seed ^= basis[bit].value;
}
}
return seed;
}
/// @brief Minimize seed xor x over subset x of values[left, right).
UInt min_xor(int left, int right, UInt seed) const {
check_range(left, right);
const auto &basis = prefixes[right];
for (int bit = bits - 1; bit >= 0; bit--) {
if (basis[bit].position >= left &&
(seed ^ basis[bit].value) < seed) {
seed ^= basis[bit].value;
}
}
return seed;
}
/// @brief Return whether value is an xor of a subset of values[left,right).
bool contains(int left, int right, UInt value) const {
check_range(left, right);
const auto &basis = prefixes[right];
for (int bit = bits - 1; bit >= 0; bit--) {
if ((value >> bit) & UInt(1)) {
if (basis[bit].position < left) {
return false;
}
value ^= basis[bit].value;
}
}
return true;
}
int dimension(int left, int right) const {
check_range(left, right);
int result = 0;
for (const entry &item : prefixes[right]) {
result += item.position >= left;
}
return result;
}
/// @brief Materialize an ordinary xor basis of a subarray.
xor_basis<UInt, bits> range_basis(int left, int right) const {
check_range(left, right);
xor_basis<UInt, bits> result;
for (const entry &item : prefixes[right]) {
if (item.position >= left) {
result.insert(item.value);
}
}
return result;
}
private:
static void insert(std::array<entry, bits> &basis, UInt value,
int position) {
for (int bit = bits - 1; bit >= 0 && value != 0; bit--) {
if (((value >> bit) & UInt(1)) == 0) {
continue;
}
if (basis[bit].value == 0) {
basis[bit] = {value, position};
return;
}
if (position > basis[bit].position) {
std::swap(value, basis[bit].value);
std::swap(position, basis[bit].position);
}
value ^= basis[bit].value;
}
}
void check_range(int left, int right) const {
assert(0 <= left && left <= right && right <= n);
}
};
} // namespace noya
#endif // NOYA_STATIC_RANGE_XOR_BASIS_HPP
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>
/// @complexity Time: O(nB) build and O(B) query for B-bit values.
/// Space: O(nB).
/// @complexity Time: O(B^2) reduced insertion and O(B) membership/min/max query.
/// Space: O(B).
namespace noya {
/// @brief Reduced linear basis over GF(2) for an unsigned integer type.
template <class UInt, int bits = std::numeric_limits<UInt>::digits>
struct xor_basis {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bits && bits <= std::numeric_limits<UInt>::digits);
std::array<UInt, bits> basis{};
int dimension = 0;
/// @brief Insert a value; return false if it is already in the span.
bool insert(UInt value) {
for (int bit = bits - 1; bit >= 0; bit--) {
if (((value >> bit) & UInt(1)) == 0) {
continue;
}
if (basis[bit] != 0) {
value ^= basis[bit];
continue;
}
basis[bit] = value;
for (int lower = 0; lower < bit; lower++) {
if ((basis[bit] >> lower) & UInt(1)) {
basis[bit] ^= basis[lower];
}
}
for (int higher = bit + 1; higher < bits; higher++) {
if ((basis[higher] >> bit) & UInt(1)) {
basis[higher] ^= basis[bit];
}
}
dimension++;
return true;
}
return false;
}
/// @brief Return whether value belongs to the represented xor span.
bool contains(UInt value) const {
for (int bit = bits - 1; bit >= 0; bit--) {
if ((value >> bit) & UInt(1)) {
value ^= basis[bit];
}
}
return value == 0;
}
/// @brief Maximize seed xor x over all represented values x.
UInt max_xor(UInt seed = 0) const {
for (int bit = bits - 1; bit >= 0; bit--) {
if ((seed ^ basis[bit]) > seed) {
seed ^= basis[bit];
}
}
return seed;
}
/// @brief Minimize seed xor x over all represented values x.
UInt min_xor(UInt seed) const {
for (int bit = bits - 1; bit >= 0; bit--) {
if ((seed ^ basis[bit]) < seed) {
seed ^= basis[bit];
}
}
return seed;
}
/// @brief Return the k-th smallest distinct value in the span, including
/// zero.
UInt kth_smallest(std::uint64_t k) const {
if (dimension < 64) {
assert(k < (std::uint64_t(1) << dimension));
}
UInt result = 0;
int index = 0;
for (int bit = 0; bit < bits; bit++) {
if (basis[bit] != 0) {
if ((k >> index) & 1) {
result ^= basis[bit];
}
index++;
}
}
return result;
}
/// @brief Insert every basis vector from another span.
void merge(const xor_basis &other) {
for (UInt value : other.basis) {
if (value != 0) {
insert(value);
}
}
}
};
/// @brief Return a basis of the intersection of two xor spans. A homogeneous
/// system is built for U*a = V*b, with one equation per value bit. Gaussian
/// elimination produces a nullspace basis; projecting its U-coordinates gives
/// an independent basis of the intersection because both input lists are
/// required to be independent.
template <class UInt, int bits = std::numeric_limits<UInt>::digits>
std::vector<UInt>
xor_space_intersection(const std::vector<UInt> &first,
const std::vector<UInt> &second) {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bits && bits <= std::numeric_limits<UInt>::digits);
const int left_size = int(first.size());
const int variable_count = left_size + int(second.size());
assert(variable_count <= 64);
xor_basis<UInt, bits> left_check;
xor_basis<UInt, bits> right_check;
for (UInt value : first) {
assert(left_check.insert(value));
}
for (UInt value : second) {
assert(right_check.insert(value));
}
std::array<std::uint64_t, bits> equations{};
for (int variable = 0; variable < variable_count; variable++) {
UInt value = variable < left_size ? first[variable]
: second[variable - left_size];
for (int bit = 0; bit < bits; bit++) {
if ((value >> bit) & UInt(1)) {
equations[bit] |= std::uint64_t(1) << variable;
}
}
}
std::array<int, 64> pivot_row{};
pivot_row.fill(-1);
int rank = 0;
for (int column = 0; column < variable_count; column++) {
int pivot = rank;
while (pivot < bits && ((equations[pivot] >> column) & 1) == 0) {
pivot++;
}
if (pivot == bits) {
continue;
}
std::swap(equations[rank], equations[pivot]);
pivot_row[column] = rank;
for (int row = 0; row < bits; row++) {
if (row != rank && ((equations[row] >> column) & 1)) {
equations[row] ^= equations[rank];
}
}
rank++;
}
std::vector<UInt> result;
for (int free_column = 0; free_column < variable_count; free_column++) {
if (pivot_row[free_column] != -1) {
continue;
}
std::uint64_t coefficients = std::uint64_t(1) << free_column;
for (int column = 0; column < variable_count; column++) {
int row = pivot_row[column];
if (row != -1 && ((equations[row] >> free_column) & 1)) {
coefficients |= std::uint64_t(1) << column;
}
}
UInt value = 0;
for (int index = 0; index < left_size; index++) {
if ((coefficients >> index) & 1) {
value ^= first[index];
}
}
result.push_back(value);
}
return result;
}
} // namespace noya
namespace noya {
/// @brief Prefix-persistent linear bases for maximum xor and membership in a
/// static subarray, with O(B) queries and O(nB) preprocessing.
template <class UInt, int bits = std::numeric_limits<UInt>::digits>
struct static_range_xor_basis {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bits && bits <= std::numeric_limits<UInt>::digits);
struct entry {
UInt value = 0;
int position = -1;
};
int n = 0;
std::vector<std::array<entry, bits>> prefixes;
static_range_xor_basis() = default;
explicit static_range_xor_basis(const std::vector<UInt> &values) {
build(values);
}
void build(const std::vector<UInt> &values) {
n = int(values.size());
prefixes.assign(n + 1, {});
for (int position = 0; position < n; position++) {
prefixes[position + 1] = prefixes[position];
insert(prefixes[position + 1], values[position], position);
}
}
/// @brief Maximize seed xor x over subset x of values[left, right).
UInt max_xor(int left, int right, UInt seed = 0) const {
check_range(left, right);
const auto &basis = prefixes[right];
for (int bit = bits - 1; bit >= 0; bit--) {
if (basis[bit].position >= left &&
(seed ^ basis[bit].value) > seed) {
seed ^= basis[bit].value;
}
}
return seed;
}
/// @brief Minimize seed xor x over subset x of values[left, right).
UInt min_xor(int left, int right, UInt seed) const {
check_range(left, right);
const auto &basis = prefixes[right];
for (int bit = bits - 1; bit >= 0; bit--) {
if (basis[bit].position >= left &&
(seed ^ basis[bit].value) < seed) {
seed ^= basis[bit].value;
}
}
return seed;
}
/// @brief Return whether value is an xor of a subset of values[left,right).
bool contains(int left, int right, UInt value) const {
check_range(left, right);
const auto &basis = prefixes[right];
for (int bit = bits - 1; bit >= 0; bit--) {
if ((value >> bit) & UInt(1)) {
if (basis[bit].position < left) {
return false;
}
value ^= basis[bit].value;
}
}
return true;
}
int dimension(int left, int right) const {
check_range(left, right);
int result = 0;
for (const entry &item : prefixes[right]) {
result += item.position >= left;
}
return result;
}
/// @brief Materialize an ordinary xor basis of a subarray.
xor_basis<UInt, bits> range_basis(int left, int right) const {
check_range(left, right);
xor_basis<UInt, bits> result;
for (const entry &item : prefixes[right]) {
if (item.position >= left) {
result.insert(item.value);
}
}
return result;
}
private:
static void insert(std::array<entry, bits> &basis, UInt value,
int position) {
for (int bit = bits - 1; bit >= 0 && value != 0; bit--) {
if (((value >> bit) & UInt(1)) == 0) {
continue;
}
if (basis[bit].value == 0) {
basis[bit] = {value, position};
return;
}
if (position > basis[bit].position) {
std::swap(value, basis[bit].value);
std::swap(position, basis[bit].position);
}
value ^= basis[bit].value;
}
}
void check_range(int left, int right) const {
assert(0 <= left && left <= right && right <= n);
}
};
} // namespace noya