可持久化字典树

数据结构 / persistent-trie

本地源文件：docs/ds__persistent-trie.md

可持久化字典树

引入

可持久化 Trie 的方式和可持久化线段树的方式是相似的，即每次只修改被添加或值被修改的节点，而保留没有被改动的节点，在上一个版本的基础上连边，使最后每个版本的 Trie 树的根遍历所能分离出的 Trie 树都是完整且包含全部信息的．

大部分的可持久化 Trie 题中，Trie 都是以 01-Trie 的形式出现的．

例题 最大异或和

对一个长度为 𝑛n 的数组 𝑎a 维护以下操作：

  1. 在数组的末尾添加一个数 𝑥x，数组的长度 𝑛n 自增 11．
  2. 给出查询区间 [𝑙,𝑟][l,r] 和一个值 𝑘k，求当 𝑙 ≤𝑝 ≤𝑟l≤p≤r 时，𝑘 ⊕⨁𝑛𝑖=𝑝𝑎𝑖k⊕⨁i=pnai 的最大值．

过程

这个求的值可能有些麻烦，利用常用的处理连续异或的方法，记 𝑠𝑥 =⨁𝑥𝑖=1𝑎𝑖sx=⨁i=1xai，则原式等价于 𝑠𝑝−1 ⊕𝑠𝑛 ⊕𝑘sp−1⊕sn⊕k，观察到 𝑠𝑛 ⊕𝑘sn⊕k 在查询的过程中是固定的，题目的查询变化为查询在区间 [𝑙 −1,𝑟 −1][l−1,r−1] 中异或定值（𝑠𝑛 ⊕𝑘sn⊕k）的最大值．

继续按类似于可持久化线段树的思路，考虑每次的查询都查询整个区间．我们只需把这个区间建一棵 Trie 树，将这个区间中的每个树都加入这棵 Trie 中，查询的时候，尽量往与当前位不相同的地方跳．

查询区间，只需要利用前缀和和差分的思想，用两棵前缀 Trie 树（也就是按顺序添加数的两个历史版本）相减即得到该区间的 Trie 树．再利用动态开点的思想，不添加没有计算过的点，以减少空间占用．

---|---

* * *

> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/ds/persistent-trie.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/ds/persistent-trie.md "edit.link.title")
>  __本页面贡献者：[Ir1d](https://github.com/Ir1d), [StudyingFather](https://github.com/StudyingFather), [H-J-Granger](https://github.com/H-J-Granger), [countercurrent-time](https://github.com/countercurrent-time), [NachtgeistW](https://github.com/NachtgeistW), [CCXXXI](https://github.com/CCXXXI), [Early0v0](https://github.com/Early0v0), [Enter-tainer](https://github.com/Enter-tainer), [AngelKitty](https://github.com/AngelKitty), [cjsoft](https://github.com/cjsoft), [diauweb](https://github.com/diauweb), [ezoixx130](https://github.com/ezoixx130), [GekkaSaori](https://github.com/GekkaSaori), [Konano](https://github.com/Konano), [LovelyBuggies](https://github.com/LovelyBuggies), [Makkiy](https://github.com/Makkiy), [mgt](mailto:i@margatroid.xyz), [minghu6](https://github.com/minghu6), [P-Y-Y](https://github.com/P-Y-Y), [PotassiumWings](https://github.com/PotassiumWings), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [sshwy](https://github.com/sshwy), [Suyun514](mailto:suyun514@qq.com), [weiyong1024](https://github.com/weiyong1024), [c-forrest](https://github.com/c-forrest), [Chrogeek](https://github.com/Chrogeek), [GavinZhengOI](https://github.com/GavinZhengOI), [Gesrua](https://github.com/Gesrua), [Henry-ZHR](https://github.com/Henry-ZHR), [hsfzLZH1](https://github.com/hsfzLZH1), [iamtwz](https://github.com/iamtwz), [kenlig](https://github.com/kenlig), [ksyx](https://github.com/ksyx), [kxccc](https://github.com/kxccc), [lychees](https://github.com/lychees), [ouuan](https://github.com/ouuan), [Peanut-Tang](https://github.com/Peanut-Tang), [REYwmp](https://github.com/REYwmp), [shuzhouliu](https://github.com/shuzhouliu), [SukkaW](https://github.com/SukkaW), [Tiphereth-A](https://github.com/Tiphereth-A), [代建杉](mailto:wood3s@foxmail.com)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用