WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
可持久化字典树 - 数据结构
可持久化 Trie 的方式和可持久化线段树的方式是相似的,即每次只修改被添加或值被修改的节点,而保留没有被改动的节点,在上一个版本的基础上连边,使最后每个版本的 Trie 树的根遍历所能分离出的 Trie 树都是完整且包含全部信息的。 大部分的可持久化 Trie 题中,Trie 都是以 01-Trie 的形式出现的。 ### " 例题[最大异或和](https://www.luogu.com.cn/problem/P4735)" > 对一个长度为 $n$ 的数组 $a$ 维护以下操作: > > 1. 在数组的末尾添加一个数 $x$ ,数组的长度 $n$ 自增 $1$ 。 > 2. 给出查询区间 $[l,r]$ 和一个值 $k$ ,求当 $l\le p\le r$ 时, $k \oplus \bigoplus^{n}_{i=p} a_i$ 。 这个求的值可能有些麻烦,利用常用的处理连续异或的方法,记 $s_x=\bigoplus_{i=1}^x a_i$ ,则原式等价于 $s_{p-1}\oplus s_n\oplus k$ ,观察到 $s_n \oplus k$ 在查询的过程中是固定的,题目的查询变化为查询在区间 $[l-1,r-1]$ 中异或定值( $s_n\oplus k$ )的最大值。 继续按类似于可持久化线段树的思路,考虑每次的查询都查询整个区间。我们只需把这个区间建一棵 Trie 树,将这个区间中的每个树都加入这棵 Trie 中,查询的时候,尽量往与当前位不相同的地方跳。 查询区间,只需要利用前缀和和差分的思想,用两棵前缀 Trie 树(也就是按顺序添加数的两个历史版本)相减即为该区间的线段树。再利用动态开点的思想,不添加没有计算过的点,以减少空间占用。 ```cpp #include
#include
#include
using namespace std; const int maxn = 600010; int n, q, a[maxn], s[maxn], l, r, x; char op; struct Trie { int cnt, rt[maxn], ch[maxn * 33][2], val[maxn * 33]; void insert(int o, int lst, int v) { for (int i = 28; i >= 0; i--) { val[o] = val[lst] + 1; // 在原版本的基础上更新 if ((v & (1 << i)) == 0) { if (!ch[o][0]) ch[o][0] = ++cnt; ch[o][1] = ch[lst][1]; o = ch[o][0]; lst = ch[lst][0]; } else { if (!ch[o][1]) ch[o][1] = ++cnt; ch[o][0] = ch[lst][0]; o = ch[o][1]; lst = ch[lst][1]; } } val[o] = val[lst] + 1; // printf("%d\n",o); } int query(int o1, int o2, int v) { int ret = 0; for (int i = 28; i >= 0; i--) { // printf("%d %d %d\n",o1,o2,val[o1]-val[o2]); int t = ((v & (1 << i)) ? 1 : 0); if (val[ch[o1][!t]] - val[ch[o2][!t]]) ret += (1 << i), o1 = ch[o1][!t], o2 = ch[o2][!t]; // 尽量向不同的地方跳 else o1 = ch[o1][t], o2 = ch[o2][t]; } return ret; } } st; int main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", a + i), s[i] = s[i - 1] ^ a[i]; for (int i = 1; i <= n; i++) st.rt[i] = ++st.cnt, st.insert(st.rt[i], st.rt[i - 1], s[i]); while (q--) { scanf(" %c", &op); if (op == 'A') { n++; scanf("%d", a + n); s[n] = s[n - 1] ^ a[n]; st.rt[n] = ++st.cnt; st.insert(st.rt[n], st.rt[n - 1], s[n]); } if (op == 'Q') { scanf("%d%d%d", &l, &r, &x); l--; r--; if (l == r && l == 0) printf("%d\n", s[n] ^ x); // 记得处理 l=r=1 的情况 else printf("%d\n", st.query(st.rt[r], st.rt[max(l - 1, 0)], x ^ s[n])); } } return 0; } ```