一、基础数据结构及其推广
这里所指的基础数据结构包括了栈、队列、链表、堆。而基于这些大家应该都会的基础数据结构又衍生出了以下很有用处的数据结构:
单调栈和单调队列：单调栈可以快速地处理出某一位置上的值在哪一段区间中作为最值出现，单调队列则可以用于优化DP，比如：
WOJ#4201 【2018NOIP提高测试1102】优美的序列（单调栈的应用）
WOJ#4764 子矩阵（单调栈的应用）
WOJ#1808 积木大赛（NOIP2013提高组）（我说这道题也可以用单调栈乱搞你信吗？）
WOJ#2735 跳房子（NOIP2017普及组）（二分+单调队列优化DP）
斜率DP也需要利用单调队列
Huffman树：构造一棵包含n个叶节点的k叉树并最小化每个叶节点权值与其深度之积之和。这个问题可以利用堆来解决，比如：
WOJ#2904 【NOI2015】荷马史诗
可并堆（左偏树）：简单来讲就是支持合并的堆。例题：
WOJ#2161 罗马游戏（可并堆模板）
WOJ#2155 派遣（虽然我用堆+启发式合并过了）
二、并查集
并查集可以用于查询一个元素属于哪一个集合，也能支持两个集合的合并。使用路径压缩的并查集均摊复杂度为O(logn)。并查集应用广泛，在最小生成树、左偏树等算法中均有用到。例题：
WOJ#3503 BZOJ1015[JSOI2008]星球大战starwar（并查集倒序维护连通块）
WOJ#4097 【2018NOIP提高测试1016】华莱士（并查集求最小生成基环树）
WOJ#2256 HDU 3018 Ant Trip（计算图的欧拉路径数目）
带权并查集：并查集的本质是维护了一个关系森林，基于这个性质，我们可以用点带权来维护其它一些信息。例题：
WOJ#2773 银河英雄传说（NOI2002）
三、ST表
利用倍增的思想，我们可以在O(nlogn)的时间内预处理，然后O(1)回答RMQ问题（区间最值问题）。例题：
WOJ#2637 超级钢琴（NOI2010）
四、树状数组
基于前缀和和差分的树状数组可以在O(logn)的时间内进行进行修改和求和，并且常数和码量都比较小。但是树状数组有一个缺点：只能支持少数几个操作。例题：
WOJ#1717 郁闷的小J（SDOI2008）
WOJ#3859 数星星 Stars
五、线段树
基于分治思想的线段树也可以在O(logn)的实间内进行修改和求和，实际上，满足结合律的问题几乎都可以用线段树解决。线段树主要考点在于如何打标记以及如何下传标记。相关例题可以看比赛：WOJ#1092 【训练】线段树（LDX题单）。
线段树还有以下应用：
Segment tree Beats：又称吉司机线段树，关于如何利用线段树进行区间取min/max的操作。例题：
WOJ#3706 最假女选手
线段树分治：目前我只会用它来维护动态图连通性。具体做法是：将询问离线，按时间顺序进行分治，并利用可撤销操作的并查集维护连通块。例题：
WOJ#4671 【2019NOIP测试12】地理课
WOJ#4492 【bzoj4025】二分图
线段树合并：还不会。例题：
WOJ#1578 天天爱跑步（NOIP2016提高组DAY1）
六、树链剖分及dfs序
通过遍历整棵树，我们可以在O(n)的时间内得到每一个点dfs的时间戳，借此将树上的一些问题转化为序列上的问题，然后就可以利用线段树等数据结构进行维护。例题：
WOJ#2231 树上修改3（dfs序模板）
WOJ#2933 阿狸的打字机（AC自动机+dfs序）
WOJ#4635 尺树寸泓
常见的树链剖分分为三类：轻重链剖分、实链剖分、长链剖分。
最为常见的是轻重链剖分。依据子树大小将儿子分为轻儿子和重儿子，在此基础上进行剖分出轻链、重链可以借此在O(logn)的时间内求出LCA或找出两点之间的路径。轻重链剖分本质是优化了的dfs序，因此也可以将树上问题转化为序列上的问题。例题：
WOJ#1457 [SCOI2016]幸运数字（树链剖分+线性基）
WOJ#3775 次小生成树（与图论算法相结合）
WOJ#4103 【模板】树链剖分（支持换根）
WOJ#4151 月下“毛景树”（边权也是可以维护的）
实链剖分：主要用于LCT。
长链剖分：按照链长进行剖分，主要用于优化DP。例题：
WOJ#4414 秘术（天文密葬法）（长链剖分+0/1分数规划）
WOJ#4317 谈笑风生
WOJ#4316 攻略
七、平衡树
平衡树基本上都是基于二叉查找树（BST）的。BST按照关键码的大小分别插入其左右子树，使得其中序遍历形成一个有序的序列，以此实现在O(logn)的时间内询问前驱、后继等操作。容易发现在子树大小差异较大的情况下BST极易退化。各类平衡树就是通过不同的方式使得BST趋于平衡。
常见的、OI要考的平衡树包括Treap、Splay、替罪羊树、非旋Treap，时间复杂度都接近于O(nlogn)。
Treap：Treap给每一个节点赋予了一个额外的由随机函数产生的权值。它通过适当的旋转操作，使得关键码满足BST的性质，同时额外权值满足堆的性质。
Splay：Splay通过一系列旋转将要进行操作的节点调整到根的位置，然后进行操作。
替罪羊树：比较暴力。定义一个平衡因子（约0.75），当两子树大小之比高于它的时候就暴力重构。
非旋Treap：不同于普通的Treap，非旋Treap并非基于旋转而是split和merge操作。
例题：
WOJ#2445 普通平衡树（各类平衡树模板）
WOJ#4730 攻城略池（平衡树+启发式合并+二分）
WOJ#2446 文艺平衡树（用Splay实现区间翻转）
八、LCT
一大难点。简单来说，LCT（Link-Cut Tree，动态树）就是实链剖分+Splay森林，即使树的形态发生改变，它也能进行维护。例题：
WOJ#2041 洞穴勘测（LCT维护连通性）
WOJ#2741 [Noi2014]魔法森林（LCT维护动态最小生成树）
WOJ#4058 tree（LCT也支持链修改）
WOJ#4492 【bzoj4025】二分图（同样可以上LCT）
九、可持久化数据结构
可持久化Trie放到字符串部分讲。
可持久化线段树：即主席树。主席树维护了每次操作之后线段树的历史形态，但难以支持修改。例题：
WOJ#1903 第k大的数（主席树模板）
WOJ#2870 【CQOI2015】任务查询系统
WOJ#4499 Spoj 10628. Count on a tree
可持久化并查集：还不会，先暂时咕咕咕。例题：
WOJ#4327 可持久化并查集加强版
可持久化Treap：同上。
十、分块及莫队算法
这两个都是时间复杂度为O(n√n)的算法。
分块采用的是“大段维护，局部朴素”的思想，效率偏低。例题：
数列分块入门系列
莫队算法可用于一类可以离线且在得到[l,r]的答案时可以在O(1)-O(logn)的时间内求得[l-1,r]和[l,r+1]的的答案的问题。例题：
WOJ#2444 小Z的袜子
十一、点分治
点分治可以在一棵树上，对具有某些限定的路径进行静态的统计。通常选取树的重心作为分治中心。例题：
WOJ#2335 树中点对统计（典例）
WOJ#2339 ak树
WOJ#4532 震波（动态点分治）
WOJ#2907 「ZJOI2015」幻想乡战略游戏（动态点分治）
十二、离线分治算法
主要包括CDQ分治和整体二分。
CDQ分治是基于时间的分治算法，即按照时间顺序对操作序列进行分治。对于操作区间[l,r]，定义mid=(l+r)>>1，我们计算[l,mid]之间的修改对[mid+1,r]之间的询问操作的贡献。CDQ分治常用来处理多维偏序问题。例题：
WOJ#3101 「BZOJ3262」陌上花开（三维偏序）
WOJ#3964 [Balkan2007]Mokia
WOJ#2063 货币兑换（CDQ分治优化斜率DP）
整体二分通过二分答案将询问进行分类，直到询问可以被回答。整体二分可以用于求解区间第k大。例题：
WOJ#2802 动态区间第k大【模板】
WOJ#4034 [Poi2011]Meteors
十三、其它
启发式合并：简而言之，就是在合并时把较小的集合插入较大的集合。例题：
WOJ#2155 派遣（堆+启发式合并）
WOJ#4730 攻城略池（平衡树+启发式合并+二分）
树套树：还不会，先咕咕咕。
KD-tree：同上。
原文：https://www.cnblogs.com/doyo2019/p/11747485.html