binary_trie.hpp¶
Multiset of fixed-width unsigned integers with xor-order queries.
Verified by ordered_set, set_xor_min.
维护整数的二进制字典树，支持插入删除、异或最值和按异或序第 k 小；适合动态 XOR 查询。
Implementation¶
#ifndef NOYA_BINARY_TRIE_HPP
#define NOYA_BINARY_TRIE_HPP 1
/// @complexity Time: O(B) per update or query for B-bit keys.
/// Space: O(NB) nodes after N distinct insertion paths.
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <vector>
namespace noya {
/// @brief Multiset of fixed-width unsigned integers with xor-order queries.
template <int Bits, class UInt = std::uint64_t> struct binary_trie {
static_assert(Bits > 0);
static_assert(Bits <= std::numeric_limits<UInt>::digits);
struct node {
std::array<int, 2> child = {-1, -1};
int count = 0;
};
std::vector<node> nodes = {node{}};
int size() const { return nodes[0].count; }
bool empty() const { return size() == 0; }
/// @brief Insert one occurrence of value in O(Bits).
void insert(UInt value) {
assert(in_range(value));
int current = 0;
nodes[current].count++;
for (int bit = Bits - 1; bit >= 0; bit--) {
int direction = int((value >> bit) & UInt(1));
if (nodes[current].child[direction] == -1) {
nodes[current].child[direction] = int(nodes.size());
nodes.push_back(node{});
}
current = nodes[current].child[direction];
nodes[current].count++;
}
}
/// @brief Erase one occurrence of value, returning whether it existed.
bool erase(UInt value) {
assert(in_range(value));
if (count(value) == 0) {
return false;
}
int current = 0;
nodes[current].count--;
for (int bit = Bits - 1; bit >= 0; bit--) {
int direction = int((value >> bit) & UInt(1));
current = nodes[current].child[direction];
nodes[current].count--;
}
return true;
}
int count(UInt value) const {
assert(in_range(value));
int current = 0;
for (int bit = Bits - 1; bit >= 0; bit--) {
int direction = int((value >> bit) & UInt(1));
current = nodes[current].child[direction];
if (current == -1 || nodes[current].count == 0) {
return 0;
}
}
return nodes[current].count;
}
/// @brief Return the k-th smallest value after xor by xor_mask.
UInt kth_xor(int k, UInt xor_mask = 0) const {
assert(0 <= k && k < size());
assert(in_range(xor_mask));
int current = 0;
UInt result = 0;
for (int bit = Bits - 1; bit >= 0; bit--) {
int mask_bit = int((xor_mask >> bit) & UInt(1));
int preferred = nodes[current].child[mask_bit];
int preferred_count = preferred == -1 ? 0 : nodes[preferred].count;
if (k < preferred_count) {
current = preferred;
} else {
k -= preferred_count;
current = nodes[current].child[mask_bit ^ 1];
result |= UInt(1) << bit;
}
assert(current != -1);
}
return result;
}
UInt min_xor(UInt xor_mask = 0) const { return kth_xor(0, xor_mask); }
UInt max_xor(UInt xor_mask = 0) const {
return kth_xor(size() - 1, xor_mask);
}
/// @brief Count values x satisfying (x xor xor_mask) < upper.
int count_less(UInt upper, UInt xor_mask = 0) const {
assert(in_range(xor_mask));
if constexpr (Bits < std::numeric_limits<UInt>::digits) {
if ((upper >> Bits) != 0) {
return size();
}
}
int current = 0;
int result = 0;
for (int bit = Bits - 1; bit >= 0 && current != -1; bit--) {
int mask_bit = int((xor_mask >> bit) & UInt(1));
int upper_bit = int((upper >> bit) & UInt(1));
if (upper_bit != 0) {
int smaller = nodes[current].child[mask_bit];
if (smaller != -1) {
result += nodes[smaller].count;
}
current = nodes[current].child[mask_bit ^ 1];
} else {
current = nodes[current].child[mask_bit];
}
}
return result;
}
private:
static bool in_range(UInt value) {
if constexpr (Bits == std::numeric_limits<UInt>::digits) {
return true;
} else {
return (value >> Bits) == 0;
}
}
};
} // namespace noya
#endif // NOYA_BINARY_TRIE_HPP
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <vector>
/// @complexity Time: O(B) per update or query for B-bit keys.
/// Space: O(NB) nodes after N distinct insertion paths.
namespace noya {
/// @brief Multiset of fixed-width unsigned integers with xor-order queries.
template <int Bits, class UInt = std::uint64_t> struct binary_trie {
static_assert(Bits > 0);
static_assert(Bits <= std::numeric_limits<UInt>::digits);
struct node {
std::array<int, 2> child = {-1, -1};
int count = 0;
};
std::vector<node> nodes = {node{}};
int size() const { return nodes[0].count; }
bool empty() const { return size() == 0; }
/// @brief Insert one occurrence of value in O(Bits).
void insert(UInt value) {
assert(in_range(value));
int current = 0;
nodes[current].count++;
for (int bit = Bits - 1; bit >= 0; bit--) {
int direction = int((value >> bit) & UInt(1));
if (nodes[current].child[direction] == -1) {
nodes[current].child[direction] = int(nodes.size());
nodes.push_back(node{});
}
current = nodes[current].child[direction];
nodes[current].count++;
}
}
/// @brief Erase one occurrence of value, returning whether it existed.
bool erase(UInt value) {
assert(in_range(value));
if (count(value) == 0) {
return false;
}
int current = 0;
nodes[current].count--;
for (int bit = Bits - 1; bit >= 0; bit--) {
int direction = int((value >> bit) & UInt(1));
current = nodes[current].child[direction];
nodes[current].count--;
}
return true;
}
int count(UInt value) const {
assert(in_range(value));
int current = 0;
for (int bit = Bits - 1; bit >= 0; bit--) {
int direction = int((value >> bit) & UInt(1));
current = nodes[current].child[direction];
if (current == -1 || nodes[current].count == 0) {
return 0;
}
}
return nodes[current].count;
}
/// @brief Return the k-th smallest value after xor by xor_mask.
UInt kth_xor(int k, UInt xor_mask = 0) const {
assert(0 <= k && k < size());
assert(in_range(xor_mask));
int current = 0;
UInt result = 0;
for (int bit = Bits - 1; bit >= 0; bit--) {
int mask_bit = int((xor_mask >> bit) & UInt(1));
int preferred = nodes[current].child[mask_bit];
int preferred_count = preferred == -1 ? 0 : nodes[preferred].count;
if (k < preferred_count) {
current = preferred;
} else {
k -= preferred_count;
current = nodes[current].child[mask_bit ^ 1];
result |= UInt(1) << bit;
}
assert(current != -1);
}
return result;
}
UInt min_xor(UInt xor_mask = 0) const { return kth_xor(0, xor_mask); }
UInt max_xor(UInt xor_mask = 0) const {
return kth_xor(size() - 1, xor_mask);
}
/// @brief Count values x satisfying (x xor xor_mask) < upper.
int count_less(UInt upper, UInt xor_mask = 0) const {
assert(in_range(xor_mask));
if constexpr (Bits < std::numeric_limits<UInt>::digits) {
if ((upper >> Bits) != 0) {
return size();
}
}
int current = 0;
int result = 0;
for (int bit = Bits - 1; bit >= 0 && current != -1; bit--) {
int mask_bit = int((xor_mask >> bit) & UInt(1));
int upper_bit = int((upper >> bit) & UInt(1));
if (upper_bit != 0) {
int smaller = nodes[current].child[mask_bit];
if (smaller != -1) {
result += nodes[smaller].count;
}
current = nodes[current].child[mask_bit ^ 1];
} else {
current = nodes[current].child[mask_bit];
}
}
return result;
}
private:
static bool in_range(UInt value) {
if constexpr (Bits == std::numeric_limits<UInt>::digits) {
return true;
} else {
return (value >> Bits) == 0;
}
}
};
} // namespace noya