binary_trie.hpp¶
维护整数的二进制字典树，支持插入删除、异或最值和按异或序第 \(k\) 小；适合动态 XOR 查询。
Complexity: Time: O(B) per update or query for B-bit keys. Space: O(NB) nodes after N distinct insertion paths.
AC 记录：ordered_set, set_xor_min。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 B, class UInt = std::uint64_t> struct binary_trie {
static_assert(B > 0);
static_assert(B <= std::numeric_limits<UInt>::digits);
struct node {
std::array<int, 2> ch = {-1, -1};
int num = 0;
};
std::vector<node> tr = {node{}};
int size() const { return tr[0].num; }
bool empty() const { return size() == 0; }
/// @brief Insert one occurrence of value in O(B).
void insert(UInt val) {
assert(in_range(val));
int cur = 0;
tr[cur].num++;
for (int bit = B - 1; bit >= 0; bit--) {
int dir = int((val >> bit) & UInt(1));
if (tr[cur].ch[dir] == -1) {
tr[cur].ch[dir] = int(tr.size());
tr.push_back(node{});
}
cur = tr[cur].ch[dir];
tr[cur].num++;
}
}
/// @brief Erase one occurrence of value, returning whether it existed.
bool erase(UInt val) {
assert(in_range(val));
if (count(val) == 0) {
return false;
}
int cur = 0;
tr[cur].num--;
for (int bit = B - 1; bit >= 0; bit--) {
int dir = int((val >> bit) & UInt(1));
cur = tr[cur].ch[dir];
tr[cur].num--;
}
return true;
}
int count(UInt val) const {
assert(in_range(val));
int cur = 0;
for (int bit = B - 1; bit >= 0; bit--) {
int dir = int((val >> bit) & UInt(1));
cur = tr[cur].ch[dir];
if (cur == -1 || tr[cur].num == 0) {
return 0;
}
}
return tr[cur].num;
}
/// @brief Return the k-th smallest value after xor by tag.
UInt kth_xor(int k, UInt tag = 0) const {
assert(0 <= k && k < size());
assert(in_range(tag));
int cur = 0;
UInt res = 0;
for (int bit = B - 1; bit >= 0; bit--) {
int mb = int((tag >> bit) & UInt(1));
int pre = tr[cur].ch[mb];
int cnt = pre == -1 ? 0 : tr[pre].num;
if (k < cnt) {
cur = pre;
} else {
k -= cnt;
cur = tr[cur].ch[mb ^ 1];
res |= UInt(1) << bit;
}
assert(cur != -1);
}
return res;
}
UInt min_xor(UInt tag = 0) const { return kth_xor(0, tag); }
UInt max_xor(UInt tag = 0) const {
return kth_xor(size() - 1, tag);
}
/// @brief Count values x satisfying (x xor tag) < hi.
int count_less(UInt hi, UInt tag = 0) const {
assert(in_range(tag));
if constexpr (B < std::numeric_limits<UInt>::digits) {
if ((hi >> B) != 0) {
return size();
}
}
int cur = 0;
int res = 0;
for (int bit = B - 1; bit >= 0 && cur != -1; bit--) {
int mb = int((tag >> bit) & UInt(1));
int ub = int((hi >> bit) & UInt(1));
if (ub != 0) {
int sm = tr[cur].ch[mb];
if (sm != -1) {
res += tr[sm].num;
}
cur = tr[cur].ch[mb ^ 1];
} else {
cur = tr[cur].ch[mb];
}
}
return res;
}
private:
static bool in_range(UInt val) {
if constexpr (B == std::numeric_limits<UInt>::digits) {
return true;
} else {
return (val >> B) == 0;
}
}
};
} // namespace noya
#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 B, class UInt = std::uint64_t> struct binary_trie {
static_assert(B > 0);
static_assert(B <= std::numeric_limits<UInt>::digits);
struct node {
std::array<int, 2> ch = {-1, -1};
int num = 0;
};
std::vector<node> tr = {node{}};
int size() const { return tr[0].num; }
bool empty() const { return size() == 0; }
/// @brief Insert one occurrence of value in O(B).
void insert(UInt val) {
assert(in_range(val));
int cur = 0;
tr[cur].num++;
for (int bit = B - 1; bit >= 0; bit--) {
int dir = int((val >> bit) & UInt(1));
if (tr[cur].ch[dir] == -1) {
tr[cur].ch[dir] = int(tr.size());
tr.push_back(node{});
}
cur = tr[cur].ch[dir];
tr[cur].num++;
}
}
/// @brief Erase one occurrence of value, returning whether it existed.
bool erase(UInt val) {
assert(in_range(val));
if (count(val) == 0) {
return false;
}
int cur = 0;
tr[cur].num--;
for (int bit = B - 1; bit >= 0; bit--) {
int dir = int((val >> bit) & UInt(1));
cur = tr[cur].ch[dir];
tr[cur].num--;
}
return true;
}
int count(UInt val) const {
assert(in_range(val));
int cur = 0;
for (int bit = B - 1; bit >= 0; bit--) {
int dir = int((val >> bit) & UInt(1));
cur = tr[cur].ch[dir];
if (cur == -1 || tr[cur].num == 0) {
return 0;
}
}
return tr[cur].num;
}
/// @brief Return the k-th smallest value after xor by tag.
UInt kth_xor(int k, UInt tag = 0) const {
assert(0 <= k && k < size());
assert(in_range(tag));
int cur = 0;
UInt res = 0;
for (int bit = B - 1; bit >= 0; bit--) {
int mb = int((tag >> bit) & UInt(1));
int pre = tr[cur].ch[mb];
int cnt = pre == -1 ? 0 : tr[pre].num;
if (k < cnt) {
cur = pre;
} else {
k -= cnt;
cur = tr[cur].ch[mb ^ 1];
res |= UInt(1) << bit;
}
assert(cur != -1);
}
return res;
}
UInt min_xor(UInt tag = 0) const { return kth_xor(0, tag); }
UInt max_xor(UInt tag = 0) const {
return kth_xor(size() - 1, tag);
}
/// @brief Count values x satisfying (x xor tag) < hi.
int count_less(UInt hi, UInt tag = 0) const {
assert(in_range(tag));
if constexpr (B < std::numeric_limits<UInt>::digits) {
if ((hi >> B) != 0) {
return size();
}
}
int cur = 0;
int res = 0;
for (int bit = B - 1; bit >= 0 && cur != -1; bit--) {
int mb = int((tag >> bit) & UInt(1));
int ub = int((hi >> bit) & UInt(1));
if (ub != 0) {
int sm = tr[cur].ch[mb];
if (sm != -1) {
res += tr[sm].num;
}
cur = tr[cur].ch[mb ^ 1];
} else {
cur = tr[cur].ch[mb];
}
}
return res;
}
private:
static bool in_range(UInt val) {
if constexpr (B == std::numeric_limits<UInt>::digits) {
return true;
} else {
return (val >> B) == 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 B, class UInt = std::uint64_t> struct binary_trie {
static_assert(B > 0);
static_assert(B <= std::numeric_limits<UInt>::digits);
struct node {
std::array<int, 2> ch = {-1, -1};
int num = 0;
};
std::vector<node> tr = {node{}};
int size() const { return tr[0].num; }
bool empty() const { return size() == 0; }
/// @brief Insert one occurrence of value in O(B).
void insert(UInt val) {
assert(in_range(val));
int cur = 0;
tr[cur].num++;
for (int bit = B - 1; bit >= 0; bit--) {
int dir = int((val >> bit) & UInt(1));
if (tr[cur].ch[dir] == -1) {
tr[cur].ch[dir] = int(tr.size());
tr.push_back(node{});
}
cur = tr[cur].ch[dir];
tr[cur].num++;
}
}
/// @brief Erase one occurrence of value, returning whether it existed.
bool erase(UInt val) {
assert(in_range(val));
if (count(val) == 0) {
return false;
}
int cur = 0;
tr[cur].num--;
for (int bit = B - 1; bit >= 0; bit--) {
int dir = int((val >> bit) & UInt(1));
cur = tr[cur].ch[dir];
tr[cur].num--;
}
return true;
}
int count(UInt val) const {
assert(in_range(val));
int cur = 0;
for (int bit = B - 1; bit >= 0; bit--) {
int dir = int((val >> bit) & UInt(1));
cur = tr[cur].ch[dir];
if (cur == -1 || tr[cur].num == 0) {
return 0;
}
}
return tr[cur].num;
}
/// @brief Return the k-th smallest value after xor by tag.
UInt kth_xor(int k, UInt tag = 0) const {
assert(0 <= k && k < size());
assert(in_range(tag));
int cur = 0;
UInt res = 0;
for (int bit = B - 1; bit >= 0; bit--) {
int mb = int((tag >> bit) & UInt(1));
int pre = tr[cur].ch[mb];
int cnt = pre == -1 ? 0 : tr[pre].num;
if (k < cnt) {
cur = pre;
} else {
k -= cnt;
cur = tr[cur].ch[mb ^ 1];
res |= UInt(1) << bit;
}
assert(cur != -1);
}
return res;
}
UInt min_xor(UInt tag = 0) const { return kth_xor(0, tag); }
UInt max_xor(UInt tag = 0) const {
return kth_xor(size() - 1, tag);
}
/// @brief Count values x satisfying (x xor tag) < hi.
int count_less(UInt hi, UInt tag = 0) const {
assert(in_range(tag));
if constexpr (B < std::numeric_limits<UInt>::digits) {
if ((hi >> B) != 0) {
return size();
}
}
int cur = 0;
int res = 0;
for (int bit = B - 1; bit >= 0 && cur != -1; bit--) {
int mb = int((tag >> bit) & UInt(1));
int ub = int((hi >> bit) & UInt(1));
if (ub != 0) {
int sm = tr[cur].ch[mb];
if (sm != -1) {
res += tr[sm].num;
}
cur = tr[cur].ch[mb ^ 1];
} else {
cur = tr[cur].ch[mb];
}
}
return res;
}
private:
static bool in_range(UInt val) {
if constexpr (B == std::numeric_limits<UInt>::digits) {
return true;
} else {
return (val >> B) == 0;
}
}
};
} // namespace noya