非持久化数据结构一般需要维护数据集最新状态，而可持久化要求查询历史状态。
可持久化Trie树
朴素：每次修改重新存一遍 \(-> MLE\)。
正解：只存被修改部分，其余不变，即第 \(i\) 次修改后，树变为第 \(i\) 次修改产生新的部分加上前 \(i-1\) 次修改产生部分。
增长同规模。
用普通线段树维护，\(m\) 次操作，时间复杂度 \(O(4n+mlog_n)\)。
可持久化线段树
例：单点修改，查询区间最大值
将 \(a[x]\) 加上 \(d\)，从表示 \(x\) 位置的叶子节点修改到根
修改时，对所有会被修改的点重开一树，树上未修改的点与新图父亲连边，被修改的点复制连边
更新 \(p\) 节点时，若 \(p\) 不为叶子，则其左右儿子之一也会被修改
假设 \(ls\) 被更新，\(ls\) 递归时，令 \(p'\) 左儿子为 \(ls'\)，右儿子为 \(rs\)
空间复杂度 \(O(4n+mlog_n)\)
由于树中每个点只有一个父亲，而可持久化线段树有多个根，所以只能用动态开点的方法编号
主席树（可持久化权值线段树）
区间第 \(k\) 小：
\(root[r]->\) 在值域区间 \([x,y]\) 的 \(cnt_1\) 值
\(root[l-1]->\) 在值域区间 \([x,y]\) 的 \(cnt_2\) 值
插入次序在 \([l,r]\) 之间，且值域在 \([x,y]\) 之间数字个数：\(cnt_1-cnt_2\)
第 \(i\) 棵线段树保存从第一次插入到第 \(i\) 次插入信息
序列问题 \(->\) 树上问题
\(tree[i]\) 表示从根节点到 \(i\) 的路径上信息（值域上区间和）
\(tree[u]+tree[v]-tree[lca]-tree[fa(lca)]\)
区间第 \(k\) 小（带单点修改）：
线段树看成树状数组上一元素
设树状数组中下标 \(i\) 所记录信息集合为 \(S_i\)，那么我们定义线段树 \(T_i\) 是维护 \(S_i\) 内信息的所有点的集合
标签：cnt,持久,值域,线段,tree,修改,数据结构 From： https://www.cnblogs.com/WYTRL/p/18369056