当先锋百科网

首页 1 2 3 4 5 6 7

二进制异或运算符的规则
7.jpg

一:可持久化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为(这些边都是有向边,从深度浅的指向深度深的,黑色节点代表根节点)

1.png

第二次

2.png

第三次

3.png

第四次

44.png

这样,一颗可持久化Trie就建好了,我们从第i个根节点开始遍历,可以扫到第1~i次加入的字符串(可以自己看看)

可持久化Trie的遍历
可持久化数据结构的重要问题就是解决区间的查询问题,比如,如果要查询第L~R次插入的字符串,该怎样从树中遍历呢?
说实话,看了网上很多大佬的写法但都不是很懂,最终还是看了李煜东的《算法竞赛进阶指南》写法看懂了
首先解决右端点的问题,直接从第R个根节点开始遍历,可以确保不会遍历到R后面的字符串,至于左端点,我们引进一个数组Max[x],叶子结点的Max就是他属于的字符串是第几次插入的,其他节点的Max就是他所在子树中的Max最大值,在访问时,如果某个节点的Max<L,则说明这个节点在L的左端,直接返回就行了
红色节点代表Max值

5.png

例如我们要访问第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总:
6.png

可持久化Trie的应用
例题: (https://https://www.acwing.com/problem/content/258/)

最大异或和的概念:
8.jpeg

普通的trie树:
9.jpg

可持久化Trie:
10.png
11.jpg

代码:

#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;
}