一种 0/1Trie 变形的数据结构
JDScript0117 · · 算法·理论
一种 0/1Trie 变形的数据结构
0x01 简介
本文讲述的是这个寒假我和 lzh 同学讨论的一种 0/1Trie 变形的数据结构，我将提供以下这道例题，来方便读者知晓这个数据结构的优缺点
\text{4s} \qquad \text{2048MB} 交互题，实现三个函数
void init(int n, vector<array<unsigned long long, 16>> a);表示给定一个长度为
n 的数组，里面每一个数的值域是[0, 2^{1024}) ，初始有n 个集合，S_i = \{a_i\} void merge(int x, int y);第
i 次调用是表示定义S_{i + n} = S_x \cup S_y ，保证每个数作为merge的参数至多一次array<unsigned long long, 16> query(int p, array<unsigned long long, 16> x);查询
\min\limits_{y \in S_p}\{x \oplus y\} ，其中\oplus 表示按位异或交互库会先调用一次
init函数，接下来混合调用m 次merge函数和q 次query函数1 \le n, q \le 5 \times 10^{5}, 0 \le m < n
1x01 0/1Trie，朴素做法
直接用 0/1Trie 维护，合并，时间复杂度为
1x02 压链 Trie，0/1Trie 的普遍优化方式
注意到我们的 Trie 上有
这样这棵 0/1Trie 就只有
排序一个数组是可以做到
但是注意到压链 Trie 的每个节点的深度依旧可以被构造到
因此，单次插入，删除的复杂度应该也是
值得一提的是，压链 Trie 在随机数据下表现优异，因为随机数据情况下树高是
综上所述，使用压链 Trie，本题的时间复杂度为
1x03 压链 Trie 在区间 min_xor 问题上的空间复杂度优化
我们知道，在 Trie 上略微做一些维护就可以做到不用可持久化做前缀 min_xor 问题，在压链 Trie 上是
于是，我们套用猫树形的结构，就可以做到
对于这道例题，如果所有合并都在查询前，应该可以使用这类方法，做到可能可以卡过的时间复杂度，和更加优秀的空间复杂度
2x01 重链剖分，对于时间复杂度的优化
先不考虑可持久化，怎么优化时间复杂度
我们先考虑值域在正常范围内，如
观察到我们在压链 Trie 上重链剖分时，我们可以通过位运算确定一个查询会从这条重链的那一位退出，应该形如
于是我们把原来的压链 Trie 中的一个重链缩成一个点，建出一个多叉树，这个树形结构的深度是
2x02 w 位分块，大值域下的解决方式
对于大值域，我们可以将原来的重链划分成很多段，每一段保证处理的位的极差不超过
在这个数据结构下，每个点的深度是
2x03 全局平衡二叉树，可持久化
发现原结构不方便可持久化的原因是它是多叉树，每个节点的空间不为
全局平衡二叉树告诉我们，对于一个树高为
所以，通过全局平衡二叉树，我们可以建出一个支持可持久化的 0/1Trie，做到树高在
3x01 中心思想和一些局限性
这个结构的主要思想是将 0/1Trie 通过变形，降低树高，达到更优的时间复杂度和可持久化空间复杂度
经过和 lzh 的讨论，认为这个结构相比于传统的 0/1Trie 或压链 Trie，存在两个比较重要且致命的局限性
- 必须提前知道 0/1Trie 内的数集，方便重剖和全局平衡二叉树的构造
- 不能做版本相减，因为没办法维护版本相减是一个节点的
and \ mask
4x01 Code
在这里放出例题用的代码，时空常数测试感觉都不大（也有可能是笔者不会造数据）
#include "stone.h"
#include <vector>
#include <algorithm>
#include <ctime>
#include <array>
#include <queue>
#define MAX_N 500000
#define WB_TREE_NODES 40000000
#define BINARY_TREE_NODES 60000000
#define inf 1000000000
unsigned long long seed;
int getRand(int l = 0, int r = 2) {
seed ^= seed << 13, seed ^= seed >> 7, seed ^= seed << 17;
return (int) (seed % (r - l)) + l;
}
void randInit() {
seed = std::time(0), getRand(), getRand(), getRand(), getRand(), getRand();
return;
}
struct OriginalTrie {
int lson, rson;
char lvl, height;
friend bool operator <(const OriginalTrie &a, const OriginalTrie &b) {
return a.lvl < b.lvl || (a.lvl == b.lvl && a.height < b.height);
}
};
struct StandardBinaryTree {
int lson, rson;
unsigned long long check_and_mask;
bool check_empty;
};
struct StandardWBranchTree {
char lvl;
unsigned long long xor_mask;
int son_rt;
};
struct BinaryTree {
int lson, rson;
};
struct WBranchTree {
unsigned long long and_mask;
bool has_empty;
int son_rt;
};
int delta, pos[MAX_N], inv_pos[MAX_N], ori_tot, sz[MAX_N - 1], stk[MAX_N - 1], len, ori_rt, std_binary_tot, std_wb_tot, binary_tot, wb_tot, rt[MAX_N << 1], versions;
bool is_all_the_same, hson[MAX_N - 1];
std::array<unsigned long long, 16> w[MAX_N];
OriginalTrie ori_trie[MAX_N - 1];
StandardBinaryTree std_binary_tree[MAX_N - 1];
StandardWBranchTree std_wb_tree[MAX_N - 1];
BinaryTree binary_tree[WB_TREE_NODES];
WBranchTree wb_tree[BINARY_TREE_NODES];
void sort(std::vector<std::array<unsigned long long, 16>> &a, int d, int l, int r) {
if (l == r || !~d) {
return;
}
unsigned long long lmt = a[inv_pos[getRand(l, r)]][d];
int ind = l;
for (int i = l; i < r; i ++) {
if (a[inv_pos[i]][d] < lmt) {
std::swap(inv_pos[ind ++], inv_pos[i]);
}
}
sort(a, d, l, ind), l = ind;
for (int i = l; i < r; i ++) {
if (a[inv_pos[i]][d] == lmt) {
std::swap(inv_pos[ind ++], inv_pos[i]);
}
}
sort(a, d - 1, l, ind), sort(a, d, ind, r);
return;
}
int dfsInit(int id) {
int lsize = ((ori_trie[id].lson >= 0) ? dfsInit(ori_trie[id].lson) : 1);
int rsize = ((ori_trie[id].rson >= 0) ? dfsInit(ori_trie[id].rson) : 1);
sz[id] = lsize + rsize, hson[id] = (lsize < rsize);
return sz[id];
}
int buildStdTree(std::vector<std::pair<std::pair<int, int>, std::pair<unsigned long long, bool>>> sons) {
std::priority_queue<
std::pair<std::pair<int, int>, std::pair<unsigned long long, bool>>,
std::vector<std::pair<std::pair<int, int>, std::pair<unsigned long long, bool>>>,
std::greater<std::pair<std::pair<int, int>, std::pair<unsigned long long, bool>>>
> heap;
for (std::pair<std::pair<int, int>, std::pair<unsigned long long, bool>> son: sons) {
heap.push(son);
}
std::pair<std::pair<int, int>, std::pair<unsigned long long, bool>> top = heap.top();
heap.pop();
while (!heap.empty()) {
std::pair<std::pair<int, int>, std::pair<unsigned long long, bool>> tmp = heap.top();
heap.pop(), std_binary_tree[std_binary_tot].lson = top.first.second, std_binary_tree[std_binary_tot].rson = tmp.first.second;
std_binary_tree[std_binary_tot].check_and_mask = tmp.second.first, std_binary_tree[std_binary_tot].check_empty = tmp.second.second;
heap.push(std::make_pair(
std::make_pair(top.first.first + tmp.first.first, std_binary_tot ++),
std::make_pair(top.second.first | tmp.second.first, top.second.second | tmp.second.second)
)), top = heap.top(), heap.pop();
}
return top.first.second;
}
std::pair<int, int> devide(int id) {
std::vector<std::pair<std::pair<int, int>, std::pair<unsigned long long, bool>>> sons;
int node = std_wb_tot ++;
std_wb_tree[node].lvl = ori_trie[id].lvl;
while (id >= 0 && ori_trie[id].lvl == std_wb_tree[node].lvl) {
int light_son = (hson[id] ? ori_trie[id].lson : ori_trie[id].rson);
if (light_son >= 0) {
sons.push_back({{sz[light_son], -1 - delta - devide(light_son).first}, {1llu << ori_trie[id].height, 0}});
} else {
sons.push_back({{1, light_son}, {1llu << ori_trie[id].height, 0}});
}
id = (hson[id] ? ori_trie[id].rson : ori_trie[id].lson);
}
if (id >= 0) {
std::pair<int, int> state = devide(id);
std_wb_tree[node].xor_mask = w[state.second][std_wb_tree[node].lvl];
sons.push_back({{sz[id], -1 - delta - state.first}, {0, 1}}), std_wb_tree[node].son_rt = buildStdTree(sons);
return {node, state.second};
}
std_wb_tree[node].xor_mask = w[id + delta][std_wb_tree[node].lvl];
sons.push_back({{1, id}, {0, 1}}), std_wb_tree[node].son_rt = buildStdTree(sons);
return {node, id + delta};
}
int makeNewNode() {
binary_tree[binary_tot].lson = binary_tree[binary_tot].rson = -inf;
return binary_tot ++;
}
int buildWBNode(int id, std::array<unsigned long long, 16> &x);
int buildBinaryNode(int id, std::array<unsigned long long, 16> &x, unsigned long long &val) {
if (id < 0) {
if (id + delta < 0) {
id = -1 - delta - buildWBNode(-1 - delta - id, x);
}
return id;
}
int node = makeNewNode();
if (val ? (val & std_binary_tree[id].check_and_mask) : std_binary_tree[id].check_empty) {
binary_tree[node].rson = buildBinaryNode(std_binary_tree[id].rson, x, val);
} else {
binary_tree[node].lson = buildBinaryNode(std_binary_tree[id].lson, x, val);
}
return node;
}
int buildWBNode(int id, std::array<unsigned long long, 16> &x) {
int node = wb_tot ++;
unsigned long long val = x[std_wb_tree[id].lvl] ^ std_wb_tree[id].xor_mask;
if (val) {
wb_tree[node].and_mask = val = 1llu << (63 ^ __builtin_clzll(val));
} else {
wb_tree[node].has_empty = 1;
}
wb_tree[node].son_rt = buildBinaryNode(std_wb_tree[id].son_rt, x, val);
return node;
}
int mergeWBTree(int S, int T);
int mergeBinaryTree(int S, int T) {
if (S == -inf || T == -inf) {
return ((S == -inf) ? T : S);
}
if (S < 0) {
if (S + delta >= 0) {
return S;
}
return -1 - delta - mergeWBTree(-1 - delta - S, -1 - delta - T);
}
int node = makeNewNode();
binary_tree[node].lson = mergeBinaryTree(binary_tree[S].lson, binary_tree[T].lson);
binary_tree[node].rson = mergeBinaryTree(binary_tree[S].rson, binary_tree[T].rson);
return node;
}
int mergeWBTree(int S, int T) {
int node = wb_tot ++;
wb_tree[node].and_mask = wb_tree[S].and_mask | wb_tree[T].and_mask;
wb_tree[node].has_empty = wb_tree[S].has_empty | wb_tree[T].has_empty;
wb_tree[node].son_rt = mergeBinaryTree(wb_tree[S].son_rt, wb_tree[T].son_rt);
return node;
}
void init(int n, std::vector<std::array<unsigned long long, 16>> a) {
for (int i = 0; i < n; i ++) {
inv_pos[i] = i;
}
randInit(), sort(a, 15, 0, n), delta = n;
for (int i = 0; i < n; i ++) {
w[i] = a[inv_pos[i]], pos[inv_pos[i]] = i;
}
for (int i = 1; i < n; i ++) {
int diff = -1;
for (int j = 15; ~j; j --) {
if (w[i][j] ^ w[i - 1][j]) {
diff = j;
break;
}
}
if (!~diff) {
continue;
}
ori_trie[ori_tot].lvl = diff, ori_trie[ori_tot].height = 63 ^ __builtin_clzll(w[i][diff] ^ w[i - 1][diff]);
if ((!len) || ori_trie[ori_tot] < ori_trie[stk[len - 1]]) {
stk[len ++] = ori_tot, ori_trie[ori_tot].lson = i - n - 1;
} else {
int tmp = stk[-- len];
ori_trie[tmp].rson = i - n - 1;
while (len && ori_trie[stk[len - 1]] < ori_trie[ori_tot]) {
ori_trie[stk[-- len]].rson = tmp, tmp = stk[len];
}
stk[len ++] = ori_tot, ori_trie[ori_tot].lson = tmp;
}
ori_tot ++;
}
if (!len) {
is_all_the_same = 1;
return;
}
ori_trie[stk[len - 1]].rson = -1, ori_rt = stk[0];
while (-- len) {
ori_trie[stk[len - 1]].rson = stk[len];
}
dfsInit(ori_rt), devide(ori_rt), versions = n;
for (int i = 0; i < n; i ++) {
rt[i] = buildWBNode(0, a[i]);
}
return;
}
void merge(int x, int y) {
if (is_all_the_same) {
return;
}
rt[versions ++] = mergeWBTree(rt[x - 1], rt[y - 1]);
return;
}
std::array<unsigned long long, 16> query(int p, std::array<unsigned long long, 16> x) {
if (is_all_the_same) {
for (int i = 0; i < 16; i ++) {
x[i] ^= w[0][i];
}
return x;
}
int standard_now = 0, now = rt[p - 1], ind = -1;
while (1) {
unsigned long long val = (x[std_wb_tree[standard_now].lvl] ^ std_wb_tree[standard_now].xor_mask) & wb_tree[now].and_mask;
if (val) {
val = 1llu << (63 ^ __builtin_clzll(val));
} else if (!wb_tree[now].has_empty) {
val = wb_tree[now].and_mask & -wb_tree[now].and_mask;
}
standard_now = std_wb_tree[standard_now].son_rt, now = wb_tree[now].son_rt;
while (standard_now >= 0) {
if (val ? (val & std_binary_tree[standard_now].check_and_mask) : std_binary_tree[standard_now].check_empty) {
standard_now = std_binary_tree[standard_now].rson, now = binary_tree[now].rson;
} else {
standard_now = std_binary_tree[standard_now].lson, now = binary_tree[now].lson;
}
}
if (standard_now + delta >= 0) {
ind = standard_now + delta;
break;
}
standard_now = -1 - delta - standard_now, now = -1 - delta - now;
}
for (int i = 0; i < 16; i ++) {
x[i] ^= w[ind][i];
}
return x;
}