可持久化数据结构
1 基本介绍
前提:所要维护的数据结构本身的拓扑结构不变。
所解决的问题:记录数据结构的所有历史版本。
核心思想:通过记录每个版本的根节点,并只记录本次与上一相邻版本不同的节点。
原则:对于之前版本信息,直接copy,而本次新的部分,必须创建新的节点以记录。
可持久化Tire树
关于本题:
所要解决的问题:
1. 序列末尾添加一个数。(此时n++)
2. 求所给区间[l, r]中任意一点i开始,ans = a[i] ^ a[i + 1] ^ ... ^ a[n] ^ x 的最大值
异或的基本知识:
1. 任何x ^ x = 0
2. 任何x ^ 0 = x
区间问题:
尝试前缀和思想
S[i] = a[1] ^ a[2] ^ ... ^ a[i]
则ans = x ^ S[n] ^ S[i - 1]
i在[l, r],i - 1在[l - 1, r - 1].且当前的x ^ S[n]固定,可视为常数C
所以问题转化为在区间(版本)[l - 1, r - 1]上找到与C相异或最大的值。
本题思路:
拿S[i]建立Tire树,没插入一次就是一个新的版本,初始版本为0.
1. 如果不设置左区间,即在区间[0, r - 1]找与C相异或最大的值。
这是用Tire数据结构能够解决的一个经典问题,只需要在第r - 1版本按位查找即可。
(注意第0个版本表示的就是0这个数字,从原问题理解:当i取1时,则表示从a[1]一直异或到a[n]^x,所以前缀和表示S[0] = 0)
2. 设置左区间后,我们则需要用max_id[]记录每个节点所涉及的S[i]中最大的i。
以此判断当前节点是否是在区间(版本)[l - 1, r - 1]内.
因为部分节点是多个版本(多个数)共用的,所以求max_id时需要综合子层的信息,取最大值
注意点
- 本题中0号版本的插入
- Tire中节点的编号从1开始,即root[0] = ++idx
- id[0] = -1,因为insert中所有的q > 1,所有0号点永远不会被更新
而对于不存在的数在Tire树上进行访问,tr[p][!v] = 0
所以id[0]起到的作用便是排除这些不存在的数的分枝。
空间大小分析
a[i]上限10^7,而2^24 = 16,777,216,对于S[i]第0位到第23位全部为1也可表示。
所以24位便足以支持,另外每个版本的根节点不算做具体位数,所以每个数需25位记录信息。
600000个数,每个数需要25个节点,所以总的节点数为600000 * 25
代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 600010, M = N * 25;
int n, m;
int root[N];
int tr[M][2], id[M], idx;
int s[N];
void insert(int i, int k, int p, int q) { // 当前待插入的数的编号i,前一个相邻版本p,当前版本q
if (k < 0) {
id[q] = i;
return ;
}
int v = s[i] >> k & 1;
if (p) tr[q][v ^ 1] = tr[p][v ^ 1]; // 当前层旧的部分,之前若存在则copy一份
tr[q][v] = ++idx; // 新的部分,必须添加
insert(i, k - 1, tr[p][v], tr[q][v]);
id[q] = max(id[tr[q][0]], id[tr[q][1]]); // 综合子层信息
}
int query(int root, int c, int L) {
int p = root;
for (int i = 23; i >= 0; --i) {
int v = c >> i & 1;
if (id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1]; // 取 ^ 比取 ! 快
else p = tr[p][v];
}
return c ^ s[id[p]];
}
int main() {
scanf("%d %d", &n, &m);
id[0] = -1; // 排除不存在数在Tire树上的分枝
root[0] = ++idx;
insert(0, 23, 0, root[0]);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
s[i] = s[i - 1] ^ x;
root[i] = ++idx;
insert(i, 23, root[i - 1], root[i]);
}
char op[2];
int l, r, x;
while (m--) {
scanf("%s", op);
if (*op == 'Q') {
scanf("%d %d %d", &l, &r, &x);
printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
} else {
scanf("%d", &x);
n++;
s[n] = s[n - 1] ^ x;
root[n] = ++idx;
insert(n, 23, root[n - 1], root[n]);
}
}
return 0;
}
请问每个节点的 编号和基础课里的一样吗, 还是每次插入一个数x, 这一条路径都是x的编号
虽然好久没敲忘记了。不过核心思想是每个节点是唯一的,所以编号也是不同的
蟹蟹~已经懂了hh, 每个节点编号不同,
id
则是序列的最大下标