可持久化Trie

可持久化Trie

可持久化Trie就是可以保存插入新字符串后的历史版本的Trie

实现

因为和线段树一样同为树形结构,因此可持久化方法几乎一样,就是只新建被影响到的链

比如最新版本有字符串abc,cos,我们插入新的字符串abcde,这样影响到的链是abc,虽然abc仍然是abc,但是c边后面加入了新边,因此这条链都受到了影响。

可持久化Trie影响

因此更新方法出来了,我们新建一个根节点 $$ root_{new} $$ ,然后把上一个版本的根节点信息拷贝给 $$ root_{new} $$ ,然后向下像普通Trie插入新节点一样,新建节点,如果上一个版本的同位节点存在,则拷贝信息给新节点,然后继续向下进行这个相同的过程直至插入完毕。

例题 BZOJ_3261


Description
给定一个非负整数序列{a},初始长度为N。

有M个操作,有以下两种操作类型:

1、Ax:添加操作,表示在序列末尾添加一个数x,序列的长度N+1。

2、Qlrx:询问操作,你需要找到一个位置p,满足l<=p<=r,使得:

a[p] xor a[p+1] xor ... xor a[N] xor x 最大,输出最大是多少。
Input
第一行包含两个整数 N  ,M,含义如问题描述所示。

第二行包含 N个非负整数,表示初始的序列 A 。

接下来 M行,每行描述一个操作,格式如题面所述。   
Output
假设询问操作有 T个,则输出应该有 T行,每行一个整数表示询问的答案。
HINT
N,M<=300000,0<=a[i]<=10^7

模型转换

首先异或操作是支持区间加减的,即支持前缀和,我们用 $$S[i]$$ 表示 $$a[1]\space xor\space a[2]\space xor\space … \space xor\space a[i]$$ ,然后 $$a[p]\space xor\space a[p+1]\space xor\space …\space xor\space a[N]\space xor\space x$$
转换为$$S[p-1]\space xor\space S[N]\space xor\space x$$。

问题转换为让我们在下标区间 $$[l-1,\space r-1]$$ 内找到一个下标 $$pos$$ (注意是减了1)使得 $$S[pos]\space xor\space (S[N]\space xor\space x)$$ 值最大,而 $$S[N]\space xor\space x$$ 对于每次询问都是一个常量,这个问题是不是十分眼熟?如果我们不考虑区间限制,而是直接在一个集合下标区间 $$[1,\space r] $$ 里找这样的 $$pos$$,就和 POJ_3764 的转换是一样的啦(即将所有数字用二进制表示,高位空处补0自高向低插入Trie,我们给一个数寻找Trie上数字异或最大值时应当优先走当前二进制位下相反的节点,然后最终走到的叶子节点代表的数字就是我们想要的答案)。

现在我们考虑 $$r-1$$ 的影响,这个限制了历史版本问题,显然我们可以通过可持久化Trie来解决

然后我们考虑 $$l-1$$ 的影响,我们界定了右端点 $$r-1$$,保证了当前树内不会有比 $$r-1$$ 新的状态进入我们的搜索范围,那么问题在于如何排除所有比 $$l-1$$ 旧的版本。在 $$r-1$$ 版本里包含了 $$l-1$$ 以前的版本和 $$l-1$$ 到 $$r-1$$ 之间的版本,模仿可持久化线段树用前缀和思想做差求增量是不现实的,那么我们考虑在节点上保存更多的信息,即每个节点带一个版本号信息保存一个节点它的子树中最新的版本下标是什么,然后在我们查询的时候我们按照 版本号大于等于 $$l-1$$ ,优先走相反位的规则进行遍历即可

注意数组要开 $$(n+m)*log(10^{7})$$ ,初始要插入一个0,为的是正确处理对1下标的询问

#include <iostream>
#include <cstdio>


const int MAXN = 300007;
const int MAXM = 300007;


int s[MAXN + MAXM];


struct Trie {
    int data[(MAXN + MAXM) * 25][2], ver[(MAXN + MAXM) * 25];

    int cntNode;
    int root[MAXN + MAXM];

    inline void insert(const int &pre_root, const int &cur_root, const int &flag, const int &str) {
        int pre = pre_root, cur = cur_root;
        for (int k = 23; k >= 0; --k) {
            ver[cur] = flag;
            const int to = (str >> k) & 1;
            if (pre != 0) data[cur][to ^ 1] = data[pre][to ^ 1];
            data[cur][to] = ++cntNode;
            cur = data[cur][to];
            pre = data[pre][to];
        }
        ver[cur] = flag;
    }

    inline int xor_search(const int &str, const int &cur_root, const int &lim) {
        int p = cur_root;
        for (int k = 23; k >= 0; --k) {
            const int to = ( (str >> k) & 1) ^ 1;
            if (ver[data[p][to]] >= lim) p = data[p][to];
            else p = data[p][to ^ 1];
        }
        return s[ver[p]] ^ str;
    }   

    inline void build(const int &flag, const int &str) {    
        root[flag] = ++cntNode;
        insert(root[flag - 1], root[flag], flag, str);
    }

} tree;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    tree.root[0] = ++tree.cntNode;
    tree.ver[0] = -1;
    tree.insert(0, tree.root[0], 0, 0);

    for (int i = 1; i <= n; ++i) {
        int tmp;
        scanf("%d", &tmp);
        s[i] = tmp ^ s[i - 1];
        tree.build(i, s[i]);
    }
    for (int i = 1; i <= m; ++i) {
        char opt[2];
        scanf("%s", opt);
        if (opt[0] == 'A') {
            int tmp;
            scanf("%d", &tmp);
            ++n;
            s[n] = tmp ^ s[n - 1];
            tree.build(n, s[n]);
        }
        else {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            printf("%d\n", tree.xor_search(k ^ s[n], tree.root[r - 1], l - 1));
        }
    }           
    return 0;
}

原文网址 : https://www.kkogoro.com/2018/07/15/可持久化trie/

知识共享许可协议
作品kkogoro采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注