可持久化简述

可持久化数据结构通常有
- Tire 字典树
- 可持久化线段树, 又称主席树。
一个数据结构可以被可持久化的前提是
- 本身的拓扑结构不会随着修改改变, 只会修改数值
可持久化的目的是
- 存储所有修改的版本, 类似于 Git, 存放数据结构的历史版本
可持久化的核心思想是
- 只记录当前版本和上一版本的区别

Tire 字典树的可持久化

最基本的 Tire 树：插入 cat, rat, cab, try

共插入了四个数据, 故会保存四个版本, 新版本只会存新加的, 旧的节点直接通过指针指代到上一个版本。

插入操作

设 p = root[idx] 为上一个版本的指针, q = root[++idx] 为新版本的指针

若 p 指向非空节点, 则需要将上一个版本的内容克隆到新版本上 tr[q] = tr[p]
若当前要新插入 $S_{i}$ , 则在 $q$ 版本中新建节点 $t r [q] [S_{i}] = + + i d x$
更新指针到下一个位置 $p = t r [p] [S_{i}], q = t r [q] [S_{i}]$

题目

题目	简介
最大异或和