[数据结构]可持久化01Trie

有一个长度为n的序列，我们支持插入操作和询问区间$[L,R]$的最大异或和 朴素的01Trie暴力会导致TLE，于是就有了专门应对区间查询的可持久化01Trie…… 通过对主席树的学习我们发现，可持久化数据结构，其实是在新建版本时新建一个根，对于本次插入，与在本次插入相反的边， 继承上一个点的子树信息，相当于继承了上个版本的前缀……  Code： （这里的$query(L, R, x)$是指求一个$res = \bigoplus_{i = l}^{r}a_i(L \leq l \leq r \leq R)$，使得$res\,xor\,x$最大，$ \bigoplus,xor$均为异或） ```cpp class Trie { private: int ch[maxn * memory_size][2], Size[maxn * memory_size], tot; //memory_size是根据总版本数确定的 public: int Root[maxn], ver;//ver是version,即当前版本编号 inline void clean() { memset(ch, 0, sizeof(ch)); memset(Size, 0, sizeof(Size)); tot = 0; ver = 0; } inline void add(int x) { int lst = Root[ver];//储存上一版本的根节点,以便记录信息 Root[++ver] = tot + 1; //本版本的根节点,由于还未判断其子树的连边情况,故写作tot + 1而非++tot for (int i = max_bit, id; i >= 0; --i)//max_bit即最大的x的位数 { Size[++tot] = Size[lst] + 1; //在循环中正式新建节点,标记长度 id = (x >> i) & 1; ch[tot][id] = tot + 1; ch[tot][!id] = ch[lst][!id];//反向边连向上一版本 lst = ch[lst][id];//在旧版本的子树中游走 } Size[++tot] = Size[lst] + 1;//新建末尾节点,标记长度 } inline void query(int L, int R, int x) { if (L > R) return 0; int nowl = Root[L - 1], nowr = Root[R], res = 0; for (int i = max_bit, id; i >= 0; --i) { id = (x >> i) & 1; if (Size[ch[nowl][!id] < Size[ch[nowr][!id]]) //贪心:如果能走反向边,就走 //判断条件:顺着左边界所在版本走到的点的长度小于右边界走到的点的长度,即保证了经过的点均在给定区间 { res += (1 << i); nowl = ch[nowl][!id]; nowr = ch[nowr][!id]; } else { nowl = ch[nowl][id]; nowr = ch[nowr][id]; } } return res; } }; ``` ~~才不会告诉你上面的代码这是[P4735 最大异或和](https://www.luogu.org/problemnew/show/P4735)的一部分~~