二进制异或运算符的规则
一:可持久化Trie的用途
正常的Trie树可以解决字符串的一些问题,特殊的Trie树(比如0/1Trie)可以解决最大异或和的相关问题,但是如果每次的询问是针对区间的,Trie树就不好解决,因为你不能对每个区间都建一棵Trie树,那样空间就会爆炸,于是,我们的可持久化Trie就登场了
二:可持久化Trie的构造
设trie[x][ch],表示从x号节点连向的字符为ch的点的编号(与普通Trie的含义相同),root[i]表示第i次插入的字符串的根节点,tot代表总节点数
可持久化Trie插入第i个字符串的构造流程如下:
1:首先新建第i个字符串的根节点,并定义两个变量p,q代表当前串的节点和上一个版本与之对应的节点,初始化p=root[i-1],q=root[i]
2:若当前字符串的下一个字符是ch,那么就让trie[q][ch]=++tot;
然后对于不是ch的字符CH,trie[q][CH]=trie[p][CH];
3:让p=trie[p][ch],q=trie[q][ch],并重复2,3,步直到建树完成
举个栗子
若待插入的字符串集为:cat,cup,soup,cut
第一次插入后的trie为(这些边都是有向边,从深度浅的指向深度深的,黑色节点代表根节点)
第二次
第三次
第四次
这样,一颗可持久化Trie就建好了,我们从第i个根节点开始遍历,可以扫到第1~i次加入的字符串(可以自己看看)
可持久化Trie的遍历
可持久化数据结构的重要问题就是解决区间的查询问题,比如,如果要查询第L~R次插入的字符串,该怎样从树中遍历呢?
说实话,看了网上很多大佬的写法但都不是很懂,最终还是看了李煜东的《算法竞赛进阶指南》写法看懂了
首先解决右端点的问题,直接从第R个根节点开始遍历,可以确保不会遍历到R后面的字符串,至于左端点,我们引进一个数组Max[x],叶子结点的Max就是他属于的字符串是第几次插入的,其他节点的Max就是他所在子树中的Max最大值,在访问时,如果某个节点的Max<L,则说明这个节点在L的左端,直接返回就行了
红色节点代表Max值
例如我们要访问第2~3次插入的字符串,则应从第3个根节点进入,如果某个节点的值大于等于Max则可以访问,红色的边和点就是可以访问的
可持久化Trie的实现
void Insert(LL t,LL len,LL pre,LL now)
{
if(len>=strlen(s[t]))
{
Max[now]=t;
return;
}
LL ch=s[t][len]-'a'+1;
if(pre)
{
for(int i=1;i<=26;i++)
trie[now][i]=trie[pre][i];//复制上一个节点
}
trie[now][ch]=++tot;
Insert(t,len+1,trie[pre][ch],trie[now][ch]);
for(int i=1;i<=26;i++)
Max[now]=max(Max[trie[now][i]],Max[now]);
}
其中t表示现在正在插入第t个字符串,len表示现在到了第len个字符,
查询类似的
y总:
可持久化Trie的应用
例题: (https://https://www.acwing.com/problem/content/258/)
最大异或和的概念:
普通的trie树:
可持久化Trie:
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 600010, M = N * 25;
int n, m;
int s[N];
int tr[M][2], id[M];
int root[N], idx;
void insert(int i, int k, int p, int q)
{
if (k < 0)
{
id[q] = i;
return;
}
int v = s[i] >> k & 1;
if (p) tr[q][v ^ 1] = tr[p][v ^ 1];
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, 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 == 'A')
{
scanf ("%d", &x);
n ++;
s[n] = s[n - 1] ^ x;
root[n] = ++ idx;
insert(n, 23, root[n - 1], root[n]);
}
else
{
scanf ("%d%d%d", &l, &r, &x);
printf ("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
}
}
return 0;
}
else
{
scanf ("%d%d%d", &l, &r, &x);
printf ("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
}
}
return 0;
}