基础数据结构

基础数据结构包括数组，链表，栈，队列等，过于基础，再次不在赘述。

并查集

普通并查集

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。首先把每个点指向的父亲结点初始化为自己，然后根据要求进行查找和合并。合并的时间复杂度是
$\Theta(1)$ 的，而查找的时间复杂度与链长有关，最坏情况下是 $\Theta(n)$
的。

路径压缩

可以发现，查找时的路径上有哪些点我们并不关心，我们只关心根结点是哪个。于是可以想到，我们在查找的时候同时把自己的父亲结点指向根结点，就可以有效的减少链的长度。这样优化后合并的时间复杂度不变，而查找的时间复杂度降为
$\Theta(\alpha(n))$ ，几乎也可以看做常数。

带权并查集

在实际问题中，我们经常需要在并查集中记录权值，然后在合并的时候特殊处理。这种问题需要根据实际情况处理。

堆

普通的堆

堆是一颗特殊的完全二叉树，堆中的结点总满足按照排序方式的不同，总是大于或小于其父亲结点，称为大根堆或小根堆（根结点最大或最小）。考虑插入一个元素，将其插入堆的末尾，然后与其父亲结点比较，如果不满足堆的性质则交换，并重复此过程直到满足堆的性质。考虑弹出根结点，将其与末尾元素交换后删除，然后让根结点与其儿子比较，如果不满足如果不满足堆的性质则交换，并重复此过程直到满足堆的性质。此方法插入和删除的时间复杂度均为
$\Theta(\log_2 n)$ 。

$STL$，$pb\text{_}ds$

在 $C++$ 的 $STL$ 和 $pb\text{_}ds$ 库中均含有 $priority\text{_}queue$
。调用后即可建堆。常数略大，但 $pb\text{_}ds$
中的一些堆时间复杂度与普通堆不同，在此不做深究。

可并堆

可并堆除了支持一般的堆的基本操作以外，还支持额外的合并操作。而可并堆有多种，包括斜堆，左偏树，二项堆，配对堆，斐波那契堆等。这里只讨论左偏树。\
左偏树是一种具有左偏性质的堆有序二叉树。每一个结点存储的信息包括左右子结点、关键值以及距离。左偏树具有以下性质：

堆的性质
$dis[u]=dis[rson]+1$ 其中叶子结点的 $dis=0$
$dis[lson]\geq dis[rson]$\
因为左偏树左偏，于是我们把所有操作放在右子树中，降低复杂度。\
合并操作是可并堆的核心操作，令 $u$ 为 $u$ ， $v$
中权值较小的一个，然后继续向下合并，在 $u$ 的右子树最右链中找到第一个比
$v$ 大的位置,将 $v$ 作为其父亲,然后继续不断递归调用合并 $v$
的右子树和以该结点为根的右子树即可,同时维护相关信息即可。若右子树 $dis$
比左子树大,则交换两个子树。\
同时，左偏树也支持删除。首先把删除结点的权值赋为 $-1$
，然后合并其左右子树得到新的左偏树，我们再把得到的这个左偏树接到删除结点的父结点上，同时维护父结点的子结点信息。但是，删除掉结点后我们可能会发现不满足左偏性质了，那么我们就需要判断是否需要交换左右子树，并且要一直向上重复判断，直到到了某一结点时左偏性质没有被破坏了或者已经到了根结点。左偏树合并的最坏时间复杂度为
$\Theta(\log_2 n)$

$\mathbf{ST}$ 表

$ST$ 表是可以在 $\Theta(n)$
的时间复杂度内求出区间最值的数据结构。首先考虑记录一段区间内的最值，最值支持区间重叠，即\
$\max{a,b,c}=\max(\max(a,b),\max(b,c))$ 考虑倍增，建立数组 $st[i][j]$
，意为从下标 $i$ 开始的连续 $2^j$ 个数的最值。显然可以用区间 $DP$
来预处理 $st[][]$ 。首先初始化 $st[i][0]=val[i]$ 状态转移方程如下：
$st[i][j]=\max(st[i][j-1],st[i+2^{j-1},j-1])$ 这样预处理时间复杂度为
$\Theta(n*\log_2 n)$ 。\
记询问区间长度为 $len$ ，我们从左端点向右找一段长为 $2^{\log_2 len}$
的区间，右端点向左也找一段长为 $2^{\log_2 len}$
的区间，显然这两段区间已经覆盖了整个区间，取最大值即可。当然为了保证询问复杂度为
$\Theta(1)$ ，我们需要提前预处理出每个
$\left\lfloor\log_2 n\right\rfloor$ 值。

树状数组

构造

树状数组是一个在线的数据结构，它可以做到在 $\Theta(\log_2 n)$
的时间复杂度内进行单点修改和区间求和。算法思路是对于一个数组 $val[]$
，建立一个树状图 $bit[]$ ，其中 $bit[i]$ 为以 $i$ 为末尾的一段长为
$lowbit(i)$ 的区间和（其中 $lowbit(i)$ 指的是 $i$ 的二进制表示中末尾的
$1$ 的权值），可以发现，一个结点加上自己的 $lowbit$
就可以找到自己的父亲结点。

单点修改 $\mathbf{modify}$

考虑单点修改，修改 $val[i]$ 的值，需要修改 $bit[i]$
以及它的祖先。就是每次修改当前结点，然后加上自己的 $lowbit$
，重复此操作直到没有父结点。由于二进制中最多有 $\log_2 n$ 个 $1$
，所以时间复杂度为 $\Theta(\log_2 n)$ 。

查询前缀和 $\mathbf{query}$

考虑询问，每次可以询问结点 $i$
的前缀和，每次将之前不重叠的区间加起来。就是每次通过减去自己的 $lowbit$
实现的。和修改一样时间复杂度为 $\Theta(\log_2 n)$ 。

线段树

构造

线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。若一个结点代表区间为
$[L,R]$ ，那么其左儿子代表的区间为 $[L,(L+R)/2]$ ，右儿子代表的区间为
$[(L+R)/2+1,R]$ ，所有叶子结点代表的区间长均为 $1$
。这样看，其实线段树也是一颗完全二叉树，所以可以用位运算来构造线段树（当然也可以动态开点）。对于一个非叶子结点
$nd$ ，可以用 $nd2$ 表示其左儿子，用 $nd2+1$ 表示其右儿子。

区间修改 $\mathbf{modify}$

单点修改其实可以归为区间修改的子问题，所以这里只讨论区间修改。考虑分块的思想，对于整个区间都要修改的结点，直接在该结点上打懒标记，对于零散的区间进行递归，找到所以需要修改的区间。线段树可以支持不止一个懒标记，但需要在下放的时候考虑顺序和相互影响。由于线段树有
$\log_2 n$ 层，所以时间复杂度为 $\Theta(\log_2 n)$ 。

区间查询 $\mathbf{query}$

和区间修改一样，同样是分块的思想。对于整个区间都在查询区间内的结点，直接加上该结点的值，零散的区间进行递归。时间复杂度同样为
$\log_2 n$ 。

权值线段树

权值线段树和线段树，唯一的本质的区别就是他们维护的东西不一样。权值线段树的下标就是值域，可能会有区间修改，区间询问，还可以打各种各样的标记。

可持久化

可持久化线段树又称主席树。用于查询区间第 $k$
大。主席树的主要思想就是：保存每次插入操作时的历史版本，以便查询区间第
$k$
大。主席树只需要支持单点修改，也就是说每次修改只会影响一条链。考虑每次修改都新建一条链，在这条链上储存新的信息。如何查询区间第
$k$ 大？考虑首先将问题简化，查询区间 $[1,R]$ 的第 $k$
大。其实我们只需要在初始时建一颗空树，然后按从小到大一次插入值，查询时找到插入
$r$
的历史版本，用权值线段树解决。在主席树中，维护的信息有前缀和的特点，所以
$[L,R]$ 区间的信息可以用 $[1,R]-[1,L-1]$ 来得到。同样用权值线段树解决。

分块

数据结构简介

分块算法实质上是一种是通过分成多块后在每块上打标记以实现快速区间修改，区间查询的一种算法。其均摊时间复杂度为
$\Theta(\sqrt{n})$ 。\
为了使得其有着最稳定的时间复杂度，我们经常讲一个长度为 $n$ 的序列分为
$\sqrt{n}$ 个大小为 $\sqrt{n}$ 的块，如果 $n$
不是完全平方数，则序列最右端会多出一个角块

区间修改 $\mathbf{modify}$

考虑修改，当我们修改任意一个区间 $[L,R]$ 时，如果 $L$ 所在的块与 $R$
所在的块相同，则直接暴力修改即可，若其不在一个块但是块是相邻的，一样是暴力修改，若其块不相邻，我们先处理两边的边块角块，最后直接修改中间块即可，三种情况时间复杂度均为
$\Theta(\sqrt{n})$ 。

区间查询 $\mathbf{query}$

和修改一样，查询的方法也是边角暴力，整块打标记。

$\mathbf{Splay}$

数据结构简介

$Splay$ ，是一种二叉排序树，它能在 $\Theta(\log_2 n)$
内完成插入、查找和删除操作。因为 $Splay$
是一颗二叉排序树，所以它的每一个结点都应该满足如下性质：

若左子树不空，则左子树上所有结点的值均小于或等于这个结点的值。
若右子树不空，则右子树上所有结点的值均大于或等于这个结点的值。\
我们知道，在对二叉树进行中序遍历时，会先遍历左子树，然后是自身，最后才是右子树。所以一颗二叉排序树的中序遍历是不严格单调递增的。我们在进行重构树时，也需要保证中序遍历不变。
$Splay$ 所有的操作时间复杂度都可以近似的看做 $\Theta(\log_2 n)$ 。

旋转操作 $\mathbf{rotate}$

核心操作。 $Splay$
通过旋转操作来保持平衡。旋转时需要保证中序遍历不变，步骤如下：

求出目标结点位于父亲结点的方向，并作为基本方向。
目标结点父亲的同向儿子 $->$ 目标结点的异向儿子。
目标结点爷爷的（左/右）儿子 $->$ 目标结点。
目标结点的异向儿子 $->$ 目标结点的父亲。

伸展操作 $\mathbf{splay}$

考虑旋转，将一个结点一直旋转至目标结点的儿子，如果目标结点为 $0$
，则表示旋转至根结点。其实只需要每次进行旋转后判断父亲是不是目标结点，如果爷爷，父亲与当前结点”三点一线”，我们就要先旋转父结点，再旋转当前结点，使这颗
$Splay$ 更平衡（这是一个很玄学的问题）。

寻找操作 $\mathbf{find}$

这是一个辅助操作，目的是把最大的小于等于指定值的结点（如果有这个值，则返回这个值，否则返回最大的小于这个值的结点）
$splay$
到根结点。操作很简单，只需要在每个结点处判断当前结点值是否小于指定值，再决定向左或向右,最后把找到的值
$splay$ 上来。

插入操作 $\mathbf{insert}$

这个操作的目的是向 $Splay$
里插入一个值。和上一个操作类似，也是需要在每个结点处判断当前结点值是否小于指定值，再决定向左或向右，如果结点存在则直接自增cnt的值。否则新建结点并与父结点连边。同时因为新建结点时可能会拉出一条链，为了保持
$Splay$ 的平衡，我们需要将该结点 $splay$ 到根。

求第 $\mathbf{k}$ 大 $\mathbf{kth}$

同样是从根结点开始向下搜，每次需要判断 $k$
与左子树大小，与（左子树大小+该结点 $cnt$
）的大小关系，再决定向左或向右，或是返回这个结点。

求排名 $\mathbf{rank}$

只需要把这个值转到根，再返回根结点左子树大小即可。

求前驱后继 $\mathbf{prev\&succ}$

求指定值的前驱（比它小的数中最大的）只需要找到左子树中最右边的那一个，返回即可。同理，求指定值的后继（比它大的数中最小的），只需要找到右子树中最左边的那一个，返回即可。

删除操作 $\mathbf{remove}$

如果把 $prev(x)\quad splay$ 到根结点，把 $succ(x)\quad splay$ 到 $prev(x)$
的右儿子，那么 $succ(x)$
的左儿子只会有目标结点一个结点，删除方法显而易见。

区间翻转 $\mathbf{reverse}$

和线段树区间加一样，这个地方也运用了”懒标记”的思想。和\
$remove$ 操作类似，将 $[L,R]$ 区间提取出来，可以把 $L-1\quad splay$
到根结点，把 $R+1\quad splay$ 到根结点的儿子，再对这个区间打上”懒标记”。

$\mathbf{Link-Cut\quad Tree}$

数据结构简介

$Link-Cut\quad Tree$
是一种用来维护动态森林连通性的数据结构，适用于动态树问题。它采用类似树链剖分的轻重边路径剖分，把树边分为实边和虚边，并用
$Splay$ 来维护每一条实路径。本质上， $Link-Cut\quad Tree$ 维护的是一个
$Splay$ 森林。 $Link-Cut\quad Tree$ 的所有操作时间复杂度均为均摊
$\Theta(\log_2 n)$ ，但常数略大。

打通操作 $\mathbf{access}$

这是 $Link-Cut\quad Tree$ 最基础的操作，意思是将点 $x$
到原树中根结点之间的链丢到一个辅助树 $Splay$ 里面。每次将 $x$ 点 $splay$
到当前所在辅助树的根节点，将它的右儿子更新为上一个 $x$ ，然后令 $x$
跳到它的父节点，特别的，第一个 $x$ 的右儿子设为 $0$ 。

找根操作 $\mathbf{findroot}$

我们可以通过 $x$ 向上找，用 $access$ 操作可以将 $x$ 和 $x$
的根结点放到一个 $Splay$ 里。又因为 $x$ 的左子树所有结点的权值 $<x<\quad x$
右子树所有结点的权值。而我们又知道，在执行完 $access$ 操作后，这课
$Splay$ 里面的结点权值最大的(深度最大的)就是 $x$
。于是我们可以将$x\quad splay$ 到这棵 $Splay$
的根结点，那么现在最左边的节点便是这课树的根结点了。

换根操作 $\mathbf{makeroot}$

具体操作是我们先将 $x$ 点与原树中的根打通一条链，那么现在它们就在同一棵
$Splay$ 里面了，可以发现 $x$
一定是在它所在的辅助树的中序遍历的最后一个的(因为它是这条链上最深的点)，我们把
$x\quad splay$ 到 $Splay$ 的根上，那么 $x$ 显然是没有右子树的，我们要实现将
$x$ 移到原树的根上，也就是将 $x$ 到根的这条链的深度全部翻转一遍，在
$Splay$ 上的体现就是将整棵树翻转一遍。

提取操作 $\mathbf{split}$

这个操作是将 $x$ 到 $y$ 之间的那条路径丢到一棵辅助树里，并且这棵辅助树以
$y$ 节点为根(方便处理信息)。 $Splay$
维护的是原树中的一条链，我们不能保证 $x$ , $y$
会在同一条链里。所以我们可以先把 $x$ 变成原树的根节点，这样 $access(y)$
就会将 $x$ 到 $y$ 之间的所有节点丢到一个 $Splay$ 中了。最后来一个把
$y\quad splay$ 到根就可以达到目的。

链接操作 $\mathbf{link}$

考虑 $Link-Cut\quad Tree$ 的本职工作：将 $x$ 和 $y$
所在树合并起来。首先将x点丢到树的根，然后去找找 $y$ 的根是不是 $x$
，如果不是说明 $x$ ， $y$ 不在一个树内，我们将 $x$ 的父节点设为 $y$
，也就相当于从 $y$ 到 $x$ 连了一条虚边。

切断操作 $\mathbf{cut}$

再考虑另一个操作，将 $x$ ， $y$ 分开。首先我们先把 $x$ ， $y$
之间的那条边用 $split$ 拎出来，因为 $x$ ， $y$ 是相邻的，所以 $y$
的左儿子一定是 $x$ ，将它们的父子关系取消即可。