简单可持久化数据结构详情
这里讲的是不加嵌套等的简单可持久化数据结构
可持久化数据结构的根本目的是为了解决多棵树存不下的问题，核心思想就是继承某个历史版本，只新增需要修改的结点。
一、可持久化线段树：
主席树能够实现区间中求k大，求满足某要求的数量等
线段树在可持久化后，原本的标记下传便不能再使用，我们往往使用标记永久化
1.[bzoj4408] [Fjoi2016]神秘数
2.fzoj2134
题解：枚举对角线，根据条件直接判断计数
3.fzoj2329
题解：第i棵线段树下标为j的表示[j,j+m)中小于等于i的个数，由于小于等于i的显然也小于等于i+1，所以可以可持久化
4.fzoj1816
题解：二分中位数x，设A[i]>=x时，B[i]=1，否则B[i]=-1，则当且仅当某个子序列之和>=0，满足中位数>=x
因为l∈[a,b],r∈[c,d]，则最大值为以l结尾的最大后缀+sum(c+1,d-1)+以r开头的最大前缀
这个过程可以可持久化，先预处理出来，然后直接询问。
5.hdu5919
题解：倒着维护每种数第一次出现的位置。
6.hdu4348
题解：标记永久化模板题
二、可持久化trie
1.可持久化trie可以实现区间异或最大值，区间中小于等于x的个数，区间第k小等
2.fzoj1819
题解：维护一下当前数为次大值时候的区间
总结：可持久化数据结构是一种很使用的工具，需根据解题需要合适使用。
相关文章
图文推荐
- 文章
- 推荐
- 热门新闻