字典树

Vision271 · 2022-07-19 10:07:12 · 个人记录

概述

• 字典树通过对边和点的巧妙定义，高效地进行字符串插入与查询。

• 字典树支持字符串插入与查询。

• 字典树单次操作的复杂度在 O(len) 级别。

实现原理：

• 边代表字符，点代表状态（已经读到的字符串）。

• 从根开始的任意一条链也可以视为一个字符串。

• 利用动态开点，仅建出字典树中有的字符串的字符对应的边（转移，参见自动机），从而保证点数上界为 \sum len。

• 查询操作：在树上一位一位地跑字符串对应字符的边。注意，此查询是“查询对应串是否在字典树内”。

• 插入操作：类似于查询，不过查到空出时建出对应点。在结尾处标记表示以这里结尾的字符串（的存在性或数量）。

• 图中红色点即为字符串结尾处，序号为字符串序号。

void ins(string &sn){
    int len=sn.size(),now=rt;
    For(i,0,len-1){
        int ch=sn[i]-'a';
        if(!e[now][ch]) e[now][ch]=++tot;
        now=e[now][ch];
    }
    ++num[now];//真结尾串
}

• 其中 num 是以某个点结尾的字符串个数。

• 有一个关于树上二分的优化：记录每个点及其子树含有多少个字符串的结尾。可加速按字典序排名查询字符串。

可持久化字典树

• 显然 trie 的插入至多开 len 个点，即最多开满一条独特链。

• 故可以模仿主席树进行维护。

• 主要用途是按位贪心，即将数按二进制拆分的方式存储，然后从上到下按位贪心。

• 什么，这个贪心不用可持久化？啊...哈哈。这是因为需要差分啦。如果给一个数列，每次询问问 l\sim r 之间的数与 v 的异或的最大值，就显然需要可持久化差分来确保对应边是能走的。

• 例题：

  • P4592 [TJOI2018]异或。

    • 就是把上面那个例子搬到了树上，重剖一下就好，反正 10^5 的数据双 \log 无所谓。

  • P4735 最大异或和。

    • 比较有意思，这个要求对那个数列进行尾端插入，然后询问的是 k\in[l,r] 的 (v\oplus sum_{k\sim n})_ {max}。

    • 两个分别来都是水题，合一起得想想。这个东西明显具备类似区间修改，准确地说这里是全局修改的性质，那能不能模仿线段树？

    • 暴力地把异或标记堆在那里显然是没有用的，根号重构乍一听不错但是我不太敢试（3e5 的根号，1.5s 也难啊）。有没有优美的解法？

    • 于是顺着在 trie 里存后缀异或和的思路继续想，反正我莫名其妙地想到了按位打反转标记。即，假如插一个 7，那么把 2^{0,1,2} 对应的边都打一个反转标记（不用真的打到边上），计算答案的时候反转一下。然后把 7 在当前的反转意义下插进去使它恰好为 7。

    • 这个做法是可以的，O(n\log v)，v 为值域。

    • 但其实有更美妙的解法...我们往 trie 里插前缀异或和，询问的时候现将询问的 v 异或上 xorsum_{r+1\sim n}，于是此时我们想要的就是 v'\oplus xorsum_{k\sim r} 的最大值，其中 k\geqslant l。

    • 稍微化一下式子：v'\oplus xorsum_{k\sim r}=ans,xorsum_{1\sim k-1}\oplus xorsum_{k\sim r}=xorsum_{1\sim r}\Rightarrow ans=v'\oplus xorsum_{1\sim r}\oplus xorsum_{1\sim k-1}。

    • 于是就变成了前缀异或和问题，随便搞了。

  • 代码不粘了，反正我参与公开计划。