首页 » 分类 » 数据结构

数据结构 | 可持久化线段树以及主席树

可持久化数据结构：总是可以保留每一个历史版本的数据结构。

可持久化线段树：可以保存每一次操作的历史版本的线段树。

可持久化权值线段树 (主席树)：可以保存每一次操作的历史版本的权值线段树。

数据结构 | 归并树

归并树 (Merge Sort Tree): 归并树是线段树和归并排序的合成，它利用线段树将归并排序的每一步都记录下来。

Kruskal 重构树：维护图上两点间所有简单路径的最大边权的最小值 / 维护树上两点间路径的最大边权的数据结构。

（也可以维护图上两点间所有简单路径的最小边权的最大值 / 维护树上两点间路径的最小边权）

线段树 (Segment Tree)：用来维护区间信息的数据结构。可在 $O (\log N)$ 的时间复杂度内完成单点修改、区间修改、区间查询（区间和、区间最大值、区间最小值）等操作。

ST 表 (Sparse Table)：对于可重复贡献问题，可在 $O (n \log n)$ 完成初始化，在 $O (1)$ 回答每个区间查询的数据结构。但是不支持修改数据。

可重复贡献问题：对于运算 $⋆$ ，如果 $x ⋆ x = x$ ，且 $⋆$ 要满足结合律，则对应的区间询问是可重复贡献问题。符合这个性质的常见运算有 $max, min, gcd$ .

哈希表 (散列表, Hash Table)：根据键而直接访问在内存储存位置的数据结构。