数据结构瞎扯

Good Morning，这里是世界第一可爱的恶魔妹妹！

自我介绍：除了这篇文章什么都不会；很菜；魔怔；不会DP题和脑筋急转弯；CF绿名，被队友带上青名；OI打铁；XCPC打铁。

文章内容：三年所学，以一个更宏观的角度展开我对数据结构的理解与总结，很多内容只是泛泛而谈，是一种形而上的理解。

面向群体：并不适合没接触过数据结构的选手，但可以先看看。默认是一些学过这些内容的选手，至少知道一些知识点的概念。

一些评价：打铁绿名选手学人写文章真的是非常丢人现眼，被锐评内容过于基础浅薄，学术垃圾。本人水平有限，就胡乱写点，看的时候可以胡乱地看。要是有错误或者补充或者一些其他的东西欢迎来一起讨论。

菜菜园子交流群：730602769

菜菜园子驻扎网站：https://www.writebug.com/group/YDAXOZyMWh

~By ProtectEMmm，2023年5月11日。

关于数据结构

按我的认知，算竞选手能力主要分为三种能力：数学能力，DP能力，DS能力。

数学能力：指数学功底和思维能力。要求选手思维足够灵活，能快速挖掘出题目的性质，推导出一些结论。

DP能力：指做DP题的能力。因为DP题十分的重要，所以这里单独列出来。

DS能力：指深厚的码力，快速DEBUG能力，建模能力，能够使用庞大的知识，经验，模板题，典题，trick魔改出一些结构方法来维护一些信息或者求得一些信息。DS能力与DS并没有什么直接关联，做图论题的能力依旧可以属于DS能力。

DS手的代码应当是OOP的。面向对象的思想能帮助DS手更好的理解数据结构，实现时能够逻辑更加清晰的组合一些知识，高内聚低耦合方便选手DEBUG，模块化接口化与题目结合防止混乱和相互影响。

DS手并不是会一些模板的选手，如果STL更加强大一些，每一个运用熟练的选手都可以取代掉只会一些模板的选手。DS手不是执着于DS的选手，而是使用DS解决问题的选手。但能够快准稳的实现各种代码并对其进行修改符合题目要求是DS手的基本素养。

数据结构在区域赛的考察中确实越来越少。现在区域赛越来越CF化，越来越倾向于考察数学能力和DP能力。杜老师说过银牌之前不需要算法。但对数据结构的学习并不是一无是处的。

在一道题目没有挖掘出关键的性质的时候，或者赛场上并没有想好该如何针对题实现代码时，可以通过一些数据结构的运用强行维护，硬性过题，并且区域赛中比较难的一些题目通常是是普通的题目组合了一些算法知识。

最后：数据结构确实减智，我也不是lxl holyk这些数据结构神仙，所以我真的很没有脑子很缺乏数学能力，并且我DP能力基本为0，我这么菜还学大佬写文章真的是非常对不起。

基础数据结构

并查集

并查集就是一个非常典型的，逻辑上是点结构，存储上是森林结构的一个结构。

并查集可以快速实现判断两个元素是否在同一个集合中和合并两个集合为一个集合。

并查集的时间复杂度，按秩合并+路径压缩后为反阿克曼函数，实际使用中可以近似看成一个常数。

一些扩展1：边带权。

一些扩展2：扩展域。例题关押罪犯。

一些扩展3：种类并查集。例题食物链。

一些扩展4：可持久化并查集。例题NOI2018归程。这题并不推荐使用可持久化并查集，可持久化并查集的应用其实较为有限，推荐这题使用kruskal重构树解决。

实际做题当中，以上内容非常少见，对于并查集一般来说只需要掌握最基础的内容就可以。并查集最常使用在染色和kruskal算法当中。

栈与队列

建议直接使用STL封装好的 stack queue deque 。

一些扩展1：单调栈。例题22女生赛A。

一些扩展2：单调队列。单调队列的一个应用：滑动窗口。例题20牛客多校第二场F是一道双重滑动窗口的题。单调队列还可以用于斜率优化时维护凸包，但我们有更好用的李超线段树。

链表

链表可以实现 O(1) 增，删，查找前驱后继。我曾经很诟病链表，我认为 O(1) 复杂度是骗人的，因为通过遍历查找到目标元素的复杂度为 O(n) 。但是后来我发现可以用数组或者一些其他的存储记录下每个元素的位置（地址），从而实现快速查找。然后就越来越感觉链表在一些特定场合下很好用了。

链表最常用的应用是找前驱后继。因为链表支持快速增删，所以对于一些结构性修改比较频繁的题目有奇效。

一些扩展1：跳表。跳表是根据对链表的改进试图模仿平衡树的一种数据结构，实际当中并没有什么作用，因为平衡树有着更好的性质和应用空间，这里提出仅作为了解。

一些扩展2：块状链表。块状链表需要支持split操作，当一些信息或者操作不方便用其他内容维护时，可以使用块状链表。例如区间翻转。但是实际使用中块状链表并没有很出色的表现，也往往可以被其他做法平替，这里提出仅作为了解。

堆

堆是一种能快速获取最值的一种结构，一般来讲只需要掌握STL中的 priority_queue 。常用于A*，Dijkstra等算法当中。

堆有着非常多的种类，例如二叉堆，配对堆，左偏树，二项堆，斐波那契堆等等。

其中一些堆支持合并，删除，修改这三种操作。但我们一般只需要掌握 priority_queue ，下面我将介绍如何使其支持合并，删除，修改。

合并：题目中的元素数量往往是固定的，因此我们可以使用启发式合并，将小堆暴力插入到大堆中，复杂度 O(log^2n)。

删除：我称这个trick为垃圾堆。原理是使用两个堆，其中一个堆用来存删除数据。每次取堆顶是判断一下是否和垃圾堆的堆顶相同，相同就pop掉。

修改：能删除就能修改，把原来的值删除掉，插入一个新的值即可。

一些扩展1：对顶堆。一个小根堆和一个大根堆顶对着顶，可以维护k固定时的第k大。对于这个操作我们有更好用的平衡树，并且k动态可变。这里提出仅作为了解。

ST表

ST 表是用于解决可重复贡献问题的数据结构。原理是一个区间永远可以拆成两个log大小的区间相交，证明考虑一个数x二进制下的最高位1所在的那一位。

一些扩展1：ST[logn][n] 的写法对于cache来说更加友好，常数更小。

一些扩展2：当序列相邻元素的绝对值只差1时存在一个加减1RMQ，也被称为四毛子，是由四个俄罗斯人发明出来的。用处比较小，这里提出仅作为了解。

一些扩展3：ST表可以扩展成正方形，矩形，甚至是三角形。三角形的ST表例题21牛客多校第五场E。

一些扩展4：ST表可以优化一个LCA做法为 O(nlogn)-O(1) 。

划分树

求区间第k大，常数上比主席树小一些。没有什么用处。

珂朵莉树

也有人称呼为ODT，老司机树。其实又是一个CNOI胡乱起名字的例子。

珂朵莉树起源于CF896C，本质上是使用某种数据结构维护连续段，而这个数据结构通常是 set 。

珂朵莉树适合处理一些区间覆盖的问题，比如区间染色。

看上去挺美好的，但是珂朵莉树有一个BUG。[l,r]这段区间在珂朵莉树上可能包含了若干个区间，假设有x个区间一次复杂度就是 O(x)。set 维护的珂朵莉树的时间复杂度只有数据随机情况下才是对的。这是早年OI在出题人造数据较水的情况下为了骗分的产物。

set 维护的珂朵莉树一点用处都没有了吗？其实不然，我们发现卡复杂度的主要原因是因为需要遍历一遍区间[l,r]覆盖的x个区间。所以如果问题只涉及到[l,r]的两个端点，不涉及到端点之间的区间，是可以使用珂朵莉树的。

这里讨论的是 set 维护的珂朵莉树，其实珂朵莉树的复杂度在数据不随机的情况下也可以正确。我们放到后面讨论。

进阶数据结构

平衡树

平衡树有很多种，能实现平衡树的作用的数据结构也有一些。这里我只介绍四种平衡树和他们的用处。

Splay：主要作用是优化LCT，但是不会Splay也没关系，因为LCT可以套板子。简单口胡一下原理，双旋操作每次可以减少树的高度，所以多次Splay操作后树的高度为log。

带旋Treap：推荐封装为一个权值树板子当STL用，这里日常抱怨一下STL为什么不维护size域。因为带旋Treap在权值树的表现上非常优秀，且码量较小，所以推荐权值树板子使用带旋Treap。简单口胡一下原理，使用随机值作为key插入到堆中，达到期望平衡。

无旋Treap：也叫FHQ-Treap。建议封装好一个无旋Treap作为序列树，无旋Treap比Splay更加的灵活，可以处理序列上的问题，也可以维护序列上的一些信息，某些场合可以替代线段树。

替罪羊树：主要是运用SGT的一种思想，这个思想在KDT上有使用到。简单口胡一下原理，一棵子树不够平衡了就重建一下这棵子树。

权值树板子是重要的，虽然权值树状数组或者权值线段树也可以替代平衡树，但是我们忽略了空间因素。树套树为了不炸空间还是需要使用平衡树。

树状数组

树状数组的灵魂在于lowbit操作，通过每个点维护[i-lowbit(i)+1,i]这个区间的一些信息，理解了这个区间就理解了一切。

对于一个区间[1,x]，我们对x进行二进制拆分。这样我们就把[1,x]拆成了log个区间。因为我们使用了二进制拆分，所以树状数组注定是一种前缀和性质的结构。

一些扩展1：快速建树。

一些扩展2：区间查询优化。

一些扩展3：高维树状数组。

一些扩展4：权值树状数组。权值树状数组就是用权值作为下标的树状数组，在一些程度上可以替代平衡树。

对于以上内容的详细讲解可以看这篇博客。

线段树

这里强调一下对线段树的重要理解：线段树=分治+记忆化+二分。

线段树每个结点维护的是一个区间里的一些信息，一个任意区间可以在线段树上被拆分为log个结点区间。

一些扩展1：一个trick。如果对线段树维护的信息的一些变化是线性的，那线段树的维护信息可以是一个矩阵，例如21南京E。这么做有一个什么好处？可以方便维护信息和lazytag，防止出错。

一些扩展2：区间合并。其实就是分治过程中的合并结果。

一些扩展3：权值线段树。权值线段树是可以一定程度上代替平衡树的，而且比树状数组要灵活很多，能干更多的事情。这是因为树状数组的左端点是定死的，是一种前缀和，所以很自然会损失一些自由度灵活性。权值线段树有一个重要的操作就是查询第k大，这里后面会展开来讲。

一些扩展4：动态开点。有时候数据不好离散化，直接建树可能高达1e9甚至更高。我们发现线段树上不是每一个区间都有用的，所以完全可以用到了再去创建这个结点，大大节约了空间。

一些扩展5：底层分块。lxl曾经教过这个内容。原理我口胡一下就是线段树最底层的一些结点其实没有什么用处，假设区间长度把小于log的结点都删去，线段树的高度就会减少loglogn层。要是查询到被删的结点怎么办？因为被删的结点区间长度都小于log所以可以直接暴力。loglogn算下来大概是4层的样子，线段树一般才20层，高度减少了20%以上。

一些扩展6：猫树。可以 O(1) 的查询区间信息。原理就是线段树每个区间都有一个mid。mid向左求后缀和，mid向右求前缀和。然后可以快速合并。

一些扩展7：李超树。李超发明的一种可以维护区间一些线段的斜率的数据结构。可以用于写斜率优化DP。原理就是维护优势线段。

一些扩展8：Segment Tree Beats，也叫吉司机线段树。可以区间取最值操作。感兴趣可以看吉老师课件。

一些扩展9：势能线段树。类似于一些操作比如对区间开根号，实际上开loglog次后一个数就变成了1，不再变化。所以对不是1的区间暴力开根，是1的区间跳过。例题区间开根。

一些扩展10：线段树分裂和线段树合并。感觉题目比较少。感兴趣可以搜一下。

一些扩展11：zkw线段树。zkw老师发明的非递归版线段树，除了常数小没有明显优势。感兴趣可以看zkw老师课件。

一些扩展12：可持久化权值线段树，也叫主席树。这个后面展开讲。

一些扩展13：树套树。这个后面展开讲。

一些扩展14：线段树二分。线段树上是可以二分的，因为线段树本质就是分治+记忆化+二分。

一些扩展15：四分树。线段树扩展到二维的情况。但是没有什么用处，因为复杂度是错误的。四分树可以看成 n^2 个点的情况下的KDT。

树状数组与线段树

这里探讨一个问题。为什么线段树比树状数组灵活？他们差在哪里了？

因为对于任意一个区间，线段树都可以拆分出log个结点区间来，而树状数组因为不断的二进制拆分所以只能拆分到右端点的某一个前缀。

但是线段树是怎么做到的呢？他比树状数组多了些什么？

答案是线段树每个结点的右儿子。线段树占用的空间是2n，树状数组占用的空间是1n，把每个结点的右儿子删掉，空间1n，变成树状数组。

这里要理解线段树的区间这个概念和树状数组的前缀这个概念。树状数组因为二进制拆分，一直求的是前缀的一些信息。树状数组=前缀。把线段树的一个局部放大来看，假设我们正在求一种信息的前缀，一个父结点，两个子节点。对于查询的右端点r，如果是父节点的r，那么父节点右儿子没有作用。如果是父节点左儿子的r，那么用上了左儿子。所以右儿子在求前缀这件事情上是没有贡献的。那如果左端点l也可以任意改变了呢？我们不妨把线段树翻转一下，发现和右端点是一样的。得出结论，左右端点都不固定的情况下需要两个儿子。

这就是线段树和树状数组的结构关系。

线段树套某些内容（树套树）

我们用几个问题来引入一下。

问题1.1：给定一个序列a，询问1次区间[l,r]的和。

遍历一遍。

问题1.2：给定一个序列a，询问q次区间[l,r]的和。

前缀和。

问题1.3：给定一个序列a，询问q次区间[l,r]的和，带修。

线段树板子题。

这三个问题一步步的深入，第三个问题中线段树的作用是什么？带着问题我们继续。

问题2.1：给定一个序列a，询问1次有多少个数比x小。

遍历一遍。

问题2.2：给定一个序列a，询问1次区间[l,r]有多少个数比x小。

遍历一遍。

问题2.3：给定一个序列a，询问q次区间[l,r]有多少个数比x小。

主席树。没错，主席树确实可以做这个题。如果要求把主席树换成普通序列上的线段树呢？

线段树每个结点套一个vector，把每个结点维护的区间的值加进去，sort一下。对于查询在每个节点的vector上二分就行。

为什么每个结点维护的vector可以排序？线段树在这里的作用是什么？带着问题我们继续。

问题3.1：给定一个序列a，询问1次比x小的最大的数是什么。

遍历一遍。

问题3.2：给定一个序列a，询问q次比x小的最大的数是什么。

sort，二分。

问题3.3：给定一个序列a，询问q次区间[l,r]比x小的数是什么。

线段树套vector，sort一下。线段树会被询问区间分割成log个结点区间，这些区间二分的答案取一个最大值就行了。

线段树在这几个问题中解决的问题是什么？为什么要使用线段树？答案是为了把询问的区间分割开。每一个线段树上的区间内部我们可以排序让其有序。

如果觉得抽象，我们考虑一下归并排序。左区间有序，右区间有序，整体可以由两个有序的区间合并出来。这是什么？分治。

线段树log个区间有序，整体可以由log个区间合并出来。线段树是什么？记忆化分治。

之所以使用线段树是因为问题上了区间，所以线段树的主要作用就是分割区间再合并。

问题3.3再加一个条件，带修。怎么办？把vector换成set。set是什么？不维护size域的平衡树。

问题2.3再加一个条件，带修。怎么办？vector换平衡树，为什么不用set？因为set没有维护size域。

这其实就是树套树，只要理解了外层线段树只是为了分割区间就理解了树套树。树状数组可不可以？当然可以，看下面内容。

线段树套线段树就是二维线段树，不过空间很容易爆炸。

可持久化权值线段树（主席树）

关于他的名字已经吵了很多年了。这里我们不讨论他的名字。

先说他能干什么？求区间第k大。权值线段树可以干什么？求第k大。区别在哪里？

假设我们对每个点开一棵权值线段树，查询区间的时候只需要遍历[l,r]范围内的权值线段树就可以了。

这么做时间有点受不了，我们有两种思路优化，这里先讲方案A。对每个前缀求一棵权值线段树。现在不用遍历区间了，前缀和减一下就行了。

但是空间上我们不是很能接受。我们发现前缀i和前缀i-1在结构上只有一条链改变了，所以我们可持久化一下。现在空间也能接受了。可持久化的作用是什么？减小空间。

A的结果就是主席树。

思考一下主席树的本质。权值线段树可以做全局第k大，如果我们能快速的拿出来一棵以查询区间为全局的权值线段树，其实还是求全局第k大。所以主席树的本质思想就是快速得到一棵区间上的权值线段树。

前面讲了线段树的作用是分割区间，那可不可以外层套一个线段树，每个结点维护那个区间的权值线段树，区间查询的时候线段树上log个结点区间合并一下？完全可以，这就是方案B。

方案B比方案A强在哪？弱在哪？

方案A用了前缀和与可持久化，所以摘出一棵权值线段树时间复杂度 O(1) ，但是可持久化让一个结点的修改变的很麻烦，因为他不一定只有一个父结点，而父结点也可能会有很多父结点，牵扯太多了。这两个结合一下适合什么题目？静态不带修。

对于方案B，每个结点维护的只是一个权值线段树，没有可持久化，所以修改起来很容易。但是对应的摘一棵树下来的复杂度为 O(logn) 。这两个结合一下适合什么题目？动态带修。

方案B就是带修主席树，可以发现和可持久化权值线段树没什么关系，但是很多人都在博客里误导说就是树套主席树。

理论上确实没问题，很美好，但是有个BUG：外层线段树太慢了，而且空间大。怎么办呢？换树状数组。

记住主席树的核心思想：快速拿出一棵权值线段树出来。在此基础上拿什么当外层都是无所谓。

我希望到目前为止已经理解一些数据结构的本质了，其实就是为了解决一些问题，用一些东西组合一下解决掉。空间太大所以我们可持久化，问题有区间所以我们上线段树，要求数据有序所以换平衡树。这就是为什么我说数据结构选手要有一些OOP的思想，这就是面向对象。

理解了上面的内容后，提问：LCT为什么使用Splay？不用Splay可不可以？Splay解决了什么问题？

不用Splay，其实就是树上一堆虚边实边的变化，Access就是把一条链的实边打通。暴力往上跳好像可以？确实可以，但是复杂度接受不了，考虑到深度是单调的，用平衡树维护并不会改变单调性（中序遍历），所以用平衡树加速一下。因为LCT不断有结构性变化，所以用Splay来抵消掉变化带来的影响，另外Splay这个旋转到根的操作很有用。

这就是数据结构本质的思想，使用一些东西来解决优化一些问题。

平衡树到珂朵莉树到线段树

上面我们说过珂朵莉树的复杂度在随机数据下才是正确的。我曾经也是这么认为的，直到我做了这道题。

思考一下珂朵莉树为什么我们认为复杂度不正确。因为需要遍历区间中的结点。放到平衡树上，等价于遍历一棵子树。

如果我们自己实现了一棵外层平衡树，通常来说是Splay或者FHQ-Treap，那么我们可以通过实现PushUp和PushDown来维护信息，这样就不需要遍历整棵子树了，复杂度就变正确了。是的这题正是使用一棵平衡树维护区间。

而珂朵莉树很多地方可以替代掉线段树。平衡树可以用来实现珂朵莉树使珂朵莉树复杂度正确。那么是否可以认为平衡树可以替代线段树呢？

事实上，线段树就是一种平衡树，线段树上的操作，基本上平衡树上都能实现。平衡树是满足偏序关系的一种树状结构，线段树的区间也满足偏序关系。

非严格数据结构

莫队

莫队解决了什么问题？用一些数据结构不是很方便维护合并一些信息，但是可以方便的添加一个元素或者删除一个元素。而两个询问[l,r]和[l,r+1]其实只改变了一个元素，那就可以快速获得了。基于此思想可以对询问进行一种合理的排序使得整体复杂度最小。

点分治

点分治的思想很类似线段树，因为他们本质都是分治。为什么点分治每次选择重心？因为这样比较平衡一些。毕竟不像区间可以选一个中点，只能选重心了。

把点分治的结构抽出来就是点分树。如果问题带修呢？那就记忆化一下。线段树每个结点里记忆化了一些东西，点分树每个结点也可以记忆化一些信息，这就是动态点分治，相关题目参考QTree4。

重链剖分

树剖可以处理很多树上问题。核心思想是挑一些链编号，链上的编号是连续的。连续的有一个什么好处呢？连续就代表区间，区间就代表线段树，所以有一类题就叫树剖线段树。而一条路径最多log条重链，也就是log个区间。log个区间在线段树上又是log个区间，所以合起来就是两个log。

DSU On Tree

有些人说这个其实就是静态链分治，不过我不会链分治所以不敢乱说。核心思想就是保留一些之前存过的信息，剩下的信息暴力获取。其实所有信息都暴力获取就是暴力，保留一些就是加了优化。保留谁的信息？重子树的信息。因为他重，所以暴力获取就慢。所以我保留他非常合理。复杂度证明用到了重剖的一些证明。

Kruskal重构树

图上一些问题有时候不需要一些没用的边，把有用的边组合成一棵树，这棵树的LCA就携带了一些特殊的性质。例题21上海H。

一些技巧和思想

扫描线

扫描线，顾名思义一条线扫过去。这条线扫的时候会经过些什么呢？用一些数据结构维护一下。一般来说是线段树，因为线段树的区间和线很接近。

CDQ分治

消序思想是很重要的做题手段。CDQ分治处理三维偏序为什么直接降了一维？因为通过分治把他们消序了。消序就是消维。还有没有其他消序的手段？枚举。例题陌上花开。

枚举消序

这么说有点抽象，结合一个实例来看。逆序对，要求i＜j但是a[i]＞a[j]。映射到二维平面，就是一个二维数点。你说这题你会了，外层套一个线段树，因为是[1,j]外层用树状数组也可以，里面维护一个平衡树，在上面讲过这东西的做法了。

确实这么做能做，但是为什么外层要套一个数据结构呢？为了多增加一个log和编码难度吗？从1到n枚举j，把已经枚举过的数插到平衡树里，这样平衡树里的数都是满足i＜j的数，统计一下多少个大于a[j]就可以了。把平衡树换成权值树状数组就是另一种逆序对的求法。

单指针

如果把枚举消序理解成单指针会有一些新的理解。比如求满足要求的区间个数。用一个单指针指向右端点。不断的通过枚举插入维护一些信息，每个右端点统计一些左端点的信息就可以计入答案了。例题22香港E。

二维数点，升维偏序

很多问题最后都可以转化到二维平面上数点的问题。举个例子，区间数颜色。一个颜色我们可能会计算多次，怎么办呢？我们给每个颜色加一维，(i,pre[i])，pre[i]表示颜色i上一次出现的下标。这样区间数颜色就是数pre[i]小于左端点的数的个数。

二维数点常和扫描线结合。

另一个例子是区间mex。mex是没出现过的最小的自然数。所以建一个权值线段树，左边小去左边反之去右边。上了区间怎么办呢？区间就是线段树，但是因为不带修所以可以主席树。每个权值维护这个权值出现的下标，就是加一维(color,index)。整体维护一下最小值。那么对于一个询问[l,r]，如果一个数的出现下标小于l那肯定就不在区间中了。我们要找的是最小的一个没出现的数，权值线段树本身就有着顺序左小右大。

离线算两次前缀和相减

其实这个也是消序的一种应用。结合例子来看。区间二维数点。

我曾经说过线段树就是用来解决区间的，但是有些时候线段树没有想的那么好用，而且空间时间未必我们能接受。

莫队。莫队有些时候确实可以做，但复杂度首先很大，而且有些信息不是很方便减。就算我们有带修莫队，回滚莫队，但还是有着局限性的。

区间二维数点，如果我们固定了左端点为1的时候，就用上面的枚举消序，其实只需要维护一个平衡树就可以了。

如果一些询问[l,r]满足前缀和性质，可以减。那么我们求出[1,r]的点数，求出[1,l-1]的点数然后减一下就可以了。

因为有些时候不好删，那我们就只能加了。怎么办？离线一下，q个询问拆成2q个询问，左端点都为1。然后对右端点排序。这样就可以用前面的枚举消序了。排序nlogn，枚举消序n，数点操作log，整体下来nlogn。例题HH的项链。

一些我不会的数据结构

KDT

必须KDT做的题目似乎并不多。

分块

如果要深入理解分块建议看lxl的200页课件，顺便做做他的Ynoi（lxl：Ynoi滞销，帮帮我们）。

分块不只有根号分块还有log值域分块，不过这不在我的讨论范围内。

手指树

好像是对序列进行一些操作。

支配树

图论中的一个知识点。

圆方树

应对仙人掌图而产生的一种结构。

字符串

AC自动机，后缀数组，fail树，回文自动机等等。

笛卡尔树

并没有什么必须使用笛卡尔树的地方感觉，平衡树就够用了。

整体二分

感觉整体二分的题都能被数据结构给硬过。

WQS二分

二分斜率本身就很抽象。并且没遇到什么题。

DAG剖分

据说是新研究出来的一种科技，要是DAG都能剖分了那以后问题就不止上树了。太恐怖了太恐怖了，希望退役前这东西不要出现。

抽象数据结构

和群论挂钩，例如线段树维护的信息是幺半群。

PQ树，析合树

不知道有什么用。

TopTree

动态树。LCT只适合维护链上的一些信息，而不适合维护子树信息。TopTree是个非常厉害的东西，基本上所有树上信息都能维护。