WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
可持久化数据结构简介 - 数据结构
author: morris821028 ## 简介 可持久化数据结构 (Persistent data structure) 总是可以保留每一个历史版本,并且支持操作的不可变特性 (immutable)。 ## 可持久化分类 ### 部分可持久化 (Partially Persistent) 所有版本都可以访问,但是只有最新版本可以修改。 ### 完全可持久化 (Fully Persistent) 所有版本都既可以访问又可以修改。 若支持将两个历史版本合并,则又称为 Confluently Persistent ## 实际应用 ### 几何计算 在几何计算中有许多离线算法,如扫描线算法一次扫过去回答所有询问,在时间复杂度分析上相当优异。但强迫在线的情况下,每一次都扫描一次,询问操作的时间复杂度就从对数时间降成线性。为了解决这一种情况,持久化技术给了另一种思维,我们将扫描线的时间轴作为一个变动依据,持久化相关的结构,只要我们能将询问在对数时间内穿梭于这个时间轴,必能动态解决先前的问题。 ### 字串处理 为了达到非常高效率的合并操作,防止大量重复性字串的生成伴随的效能退化,使得各方面的操作都能远低于线性操作。如 C++ rope 就是一个持久化的数据结构。不只是字串操作,若处理类型有大量重复的情况,持久化的概念便能派上用场。 ### 版本回溯 实际上就是对应大部分的应用软体中的 redo/undo。如果资料库/操作变动为了高效率操作而会配上复杂的结构(并不像 hash, set 反转操作只需要常数或对数时间),那么为了快速回推变动结果,持久化结构就是要减少 redo/undo 的花费。 资料库本身可以常数回推,纪录变动的部分情况即可。而应用层的计算,大部分实作都是砍掉快取,并且重新计算出一份新的结构,有时候回推的变动大小为 m,为了重新计算结构而消耗了 n+m,如果 n 和 m 的差距非常大,那连续回推的体感就很糟糕。 ### 函数式编程 函数式编程需要特别的数据结构以符合语言特性,其中不可变的性质更为重要,以利于并行环境与除错。如面向对象编程的 Java 8 后引入 stream 类,支援写出函数式的语法设计,可提供惰性求值、无限值域等的特殊功能。 ## 参考 -
- MIT 课程