转载自South_wind的专栏常见的数据结构运用总结考虑到Obsidian三个成员的擅长领域，这段时间都在做杂题，算是学习各种算法吧，趁现在休息的时间，而且大家马上要备战今年的比赛了，写写自己专攻方面的一些心得吧扯开线段树、平衡树这些中高级的东西，先说说基础的数据结构栈算是代码量最小的数据结构？出栈进栈都只有一句话而已常见用途：消去一个序列中的相同元素(做法大家应该都知道了吧，见过很多次了)维护一个单调的序列(所谓的单调栈，dp的决策单调？)表达式求值(经典的栈运用，如果使用的很熟悉的话，可以处理一元、二元运算，不过最近没见过类似的题目了)用于辅助其他算法(计算几何中的求凸包)队列队列应该还是很常见的数据结构了，如果专攻图论的话，spfa应该是写烂了的这里说到的队列，是狭义的普通的队列和循环队列，不包括后面讲的一些变形注意循环队列的写法，尽量不要使用取模运算，不然的话，遇到不厚道的出题者，可以把取模的循环队列卡到死常见用途：主要用于辅助其他算法，比如说spfa，bfs等(建议习惯用stl的孩子手写queue，毕竟就几行代码而已，偷懒会付出代价的。
)双端队列如果写dp写的多的话，这个东西应该还是算是比较基础的东西了，双端队列多用于维护一个满足单调性的队列还是建议手写，stl的deque使用块状链表写的，那东西的复杂度是O(Nsqrt(N))的，不要被迷惑了。
常见用途：dp的单调性优化，包括单调队列优化和斜率优化，都要用到这个结构计算几何中的算法优化，比如半平面交树的分治问题中利用单调队列减少转移复杂度链表Dancing Links写图论的不要告诉我不会写这货，链表可以写单双向，循环非循环的，高级点儿的可以考虑十字链表，麻花链表不过链表可以说是树形结构的基础，如果这个掌握的不好，那么树形结构写起来就会很纠结链表的优势在于可以O(1)的插入删除，如果要求插入的位置只是在序列的两端的话，这个数据结构是最方便的了(无视双端队列)hash表就是用链表实现的，熟悉hash的同学可以试试看怎么使你的hash效率提高常见用途：图的邻接表，维护不确定规模的二维数组约瑟夫问题，复杂度O(NlogN)单纯考链表的题目，比如说类似文本编辑器的东西算法实现上辅助，比如说POJ3183搜索优化，最经典的就是Dancing Links维护路径，嗯，这类问题就比较恶心了，有两题都是类似的问题，题的名字都叫做植物大战僵尸……字典树自动机字典树又称为前缀树，用于维护一系列串(不一定是字符串，可以把一个数字看成二进制串，k进制串等)，我们可以通过字典树解决很多关于串的问题常见用途：字符串匹配(最基础的用途了吧)字符串hash(利用字典树可以在O(N)的时间内查出一个串是否在集合中，N是串的长度)构建dp转移矩阵(其实很多题目都是利用自动机构建转移矩阵，然后矩阵快乘的，这也算是比较基础的运用了)字符串在自动机上的dp(这个是很大的一块，算是自动机最大的运用点)堆优先队列堆在这段时间运用的次数明显增加了很多，自从某学校出了那计算几何扫描线之后，大家对这个数据结构不像原来那么陌生了普通堆代码量在20到30行左右，如果需要支持更改权值，删除特定结点的操作的话，需要改点堆，代码会多那么10行左右大家对于堆的最早理解，可能就是堆优化dij了，这个也算是它的一个很重要的运用吧常见用途堆优化dijkstra(很经典的运用)极角扫描线(详见Visible Segments)某些贪心的题(我记得ZOJ月赛出过好几次的？CF也有类似的题目，还有一题经典的倒水问题HDU1692)堆优化的prim(已经很久没见过非要这么写的题目了，最经典的问题是最优比例生成树)搜索中的优化(大家都懂得，A*算法基于优先队列)满足偏序关系的集合(其实极角扫描线算是这个的一个子类了，很多问题可以转化过来)并查集这个东西应该在关于树的问题中非常常见了，用在非常多关于集合的合并问题上常见用途：离线LCA(tarjan算法的精髓就是并查集)集合维护，比如说POJ的食物链和我们OJ的Food，这个算是扩展并查集的经典运用之一几类可以用基础数据结构解决的经典树上统计问题求一颗树中任意两点间的距离，我们可以离线LCA，利用并查集维护点到父亲结点的距离，每次找到LCA之后，在LCA结点拉一个处理链表，回溯到LCA的时候处理全部以这个点为LCA的所有查询。
静态查询一棵树某条路径上的最大最小边权，利用并查集维护点到其父亲结点这条路径上的最大边权即可。
给你一棵树，叫你求一条有向路径上前面一个点减去后面一个点的点权差值最大，依然是扩展并查集，怎么实现大家自己想吧。
还有一题是HDU的3804，很经典的题目，这题可以用四种不同的方法过，大家有兴趣的可以YY一下。
基础的数据结构告一段落，下面主要讲讲线段树和树状数组的运用吧，直接说常见用途了，毕竟这个大家用的太多了常见用途(不扩展)：dp优化(非常多的dp问题可以用树状数组和数据结构来优化，比如说我们校赛初赛和决赛的某题，dp专题的某题，还有LIS的O(NlgoN)优化等等)括号序列、树的线性序列统计问题(之前发过了，就不扩展了)更新点查找区间，更新区间查找点这个经典问题都是可以利用树状数组来做的，可以说树状数组太强大了，代码短常数小，如果遇到此类的问题，那就是裸的不能再裸了，专攻数据结构的，需要对这类问题的经典模型尽量多的进行掌握。
这类问题最常见的用处就是求逆序对(HDU1394)和求一个区间内一堆直线相交的个数(保证不会有三条直线交于一点，例子ZOJ3157) URAL1470，三维树状数组，其实和二维没啥区别，就是要抓住如何更新树状数组的经典运用有两题经典题，一个是POJ2828，一个是HDU3436，后者是前者的动态版，如果可以自己想出这两题的做法，基本上基础的树状数组题目是没有问题了。
更新区间查找区间这类问题一般是不能使用树状数组来做的(那啥用差分求区间和的无视，那种只是特例而已)，一般正式比赛考察的比较多的就是这类问题，非常重视对懒操作的实现，一般建议大家写一个上传和一个下放函数，即使是就一行，写到函数中，扩展起来可以更方便。
如果想锻炼自己对数据结构的掌握程度，可以尝试利用树状数组和线段树来做Memory Control这题，如果能想出三种或者三种以上的状态定义方法，就基本上合格了。
另外还有一题非常好的考察基本功的题目，是HDU1199，一般的离散化是会有问题的，就看大家怎么写了。
对于懒操作考察的另外一题是POJ3225，算是比较经典的区间翻转的范例了。
如果以上的题目都解决了，就去写zhymaoiing的Rain in the ACStar吧，我们OJ就有，这题写了基本上对计算几何和数据结构的综合就有感觉了。
最后建议大家去写写SPOJ的GSS系列和QTREE系列，这两个系列在后面会专门提到。
扫描线这种问题主要遇到的模型有以下几种，括号中是对应的时间复杂度给你N个矩形，求矩形的并面积(O(NlogN))给你N个矩形，求矩形的并周长(O(NlogN))给你N个矩形，每一个矩形有一定的权值，权值最多有K种，求加权的面积并，其中重叠部分用最大权值计算(O(NKlogN))给你N个矩形，叫你求被覆盖恰好K次或者至少K次的面积(O(NKlogN))给你N个矩形，每一个矩形有一定的权值，权值最多有K种，求加权的面积并，其中重叠部分用特定的公式计算混合权值(O(2^K*NlogN)) 给你N个点，用一个矩形覆盖最多的点(O(NlogN))给你N个点，M个矩形，询问每一个点是否被包含在任意一个矩形中(O((N+M)log(N+M)))给你N个点，点分为可选点和不可选点，询问用一个矩形覆盖的最多可选点的数量，任何不可选点都不能被覆盖，询问覆盖最多点的方案数(O(NlogN))*树链剖分QTREE这个是很大的一块，但是也是很恶心的一块内容，如果你觉得自己基础的问题都没有了的话，可以考虑两个选择，一个是学习这个，另外一个就是做做GSS熟练剖分详看漆子超的论文，具体实现就不讲了，常见的题目，最经典还是SPOJ的QTREE系列了，这个对代码能力的要求还是很苛刻的，在比赛中，如果遇到这类问题，如果又没有强大的代码能力，又没有足够的时间，那就不要去碰它吧。
此外剖分推荐GSS7，经典题之一。
我做过的剖分题的列表：SPOJ QTREE1-4 HDU3601 POJ3237 ZJOI2008树的统计SPOJ GSS7 HDU3804(如果想写就写吧，这题不用剖分的) HDU3966(依然是一道可以不用剖分的题目)*GSS系列解释GSS系列是SPOJ的经典线段树题了，其中1、3、5是基础的题目，建议大家在学习了线段树后作为强化用，GSS2和GSS7，其中GSS2是一个非常经典的模型，建议大家花一周的时间慢慢啃，如果自己思维好的话，有可能一个下午想出做法，不过那个题不是想出来就能写出来的。
GSS7是一个剖分，算是裸的题目了，就是维护的量太多，建议大家代码能力提高之后再来写写。
GSS6不是基础的数据结构题，我将在后面提到这题。
以上的数据结构可以覆盖区域赛的中低档题，其中GSS2如果在区域赛中，完全可以算是难题了(前提是没见过此类问题)，对于区域赛中，这些数据结构可以说占了90%以上下面是一些偏们的数据结构和一些高级数据结构的介绍划分树划分树是一个可以在O(NlogN)时间内求出每一个子区间内第K小的数的数据结构，可以算是模板化的东西了，经常和树状数组结合来考察，不过考的不多，所以建议如果专攻数据结构的可以考虑学习一下，但是不要太过于钻难题。
左偏树斜堆两类经典的可合并堆，可以在O(NlogN)时间内对数集进行合并，维护最值，建议学习一个，不建议都学习，我觉得没必要。
块状链表可以说在Splay没有出来的年代，这个是万能的武器，在O(Nsqrt(N))的时间内可以进行序列的翻转、查询操作，可以算是非常无敌了，但是在Splay出来了之后基本上就被遗弃了，不过块状链表的思想是非常好的，CF经常考察利用块状链表做的题目，要学习的话，就专门去看看其思想吧跳表这个利用链表进行优化的数据结构，基本上没啥用处，不过可以提提，时间复杂度是均摊的，没有发现一定要这个数据结构解决的问题平衡树平衡树可以做几乎所有关于数集的维护操作，常见的平衡树有SBT和Splay，一般的话，建议如果专攻数据结构的可以在巩固了基础数据结构的基础上，学学这两种平衡树。
对这两种结构进行比较，Splay的功能和SBT比起来，强大了不止一个档次，但是相应地，其代码量也大了不止一个档次。
按照我的代码风格，SBT的代码一般维持在150行左右，但是非要Splay来写的题目，一般代码量会超过200行，甚至超过300行。