可持久化数据结构 编辑
在计算机编程中，可持久化数据结构是一种能够在修改之后其保留历史版本的数据结构。这种数据结构实际上是不可变物件，因为相关操作不会直接修改被保存的数据，而是会在原版本上产生一个新分支。这个术语是在1986年Driscoll、Sarnak、Sleator和Tarjans的文章中提出的。
1
相关
可持久化线段树是一种可持久化数据结构。这种数据结构在普通线段树的基础之上支持查询某个历史版本，同时时间复杂度与线段树是同级，空间复杂度相较而言更高。在中国信息学奥林匹克竞赛中，由于引入者黄嘉泰姓名的缩写与前中共中央总书记、国家主席胡锦涛相同，因此这种数据结构也可被称为总书记树或主席树。
可持久化线段树是一种可持久化数据结构。这种数据结构在普通线段树的基础之上支持查询某个历史版本，同时时间复杂度与线段树是同级，空间复杂度相较而言更高。在中国信息学奥林匹克竞赛中，由于引入者黄嘉泰姓名的缩写与前中共中央总书记、国家主席胡锦涛相同，因此这种数据结构也可被称为总书记树或主席树。