数据结构知识（一）

并查集是一个森林形的数据结构。
将一个元素抽象为一个图中的结点，保证同属一个集合的元素包含在同一棵树中，而不在同一个集合的元素分属不同的树。

初始化：

for (int i = 1; i <= n; ++i) 
    p[i] = i; 

将两个元素所在集合合并，就是把一个树根连到另一个树上。
注意：只能合并两个不同的集合！

判断条件，合并这里就不写了，主要讲讲改进：

路径压缩：

事实上，我们不关心树具体是什么样子，而只关心每个结点的根祖先是什么。
所以，当访问到一条长链时，不妨让链上元素都直接连到根结点上。

其实也是p[x] 与 x的关系

带权并查集：

int find(int x)
{
    if (p[x] != x)
    {
        int root = find(p[x]);
        d[x]  (操作) = d[p[x]];
        p[x] = root;
    }
    return p[x];
}

第二行取出节点 x 的根，并更新 x 的未更新的祖先。

接下来我们来更新 x 。此时 p[x] 还未改变，我们 x 通过运算继承其父节点（马上不是了）的值。因为 d[p[x]] 已经是被更新过的新的值，一定正确，可以进行操作。

最后，我们来路径压缩，让 x 直接指向它的祖先就好了。

AC自动机： trie + kmp

其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话会很浪费时间,

所以AC自动机应运而生,如同Manacher一样,AC自动机利用某些操作阻止了模式串匹配阶段的回溯,将时间复杂度优化到了O ( n ) - n 为文本长度。

1.构造一棵Trie，作为AC自动机的搜索数据结构。

2.构造ne指针，使当前字符失配时跳转到具有最长公共前后缀的字符继续匹配。如同 KMP算法一样， AC自动机在匹配时如果当前字符匹配失败，那么利用ne指针进行跳转。由此可知如果跳转，跳转后的串的前缀，必为跳转前的模式串的后缀并且跳转的新位置的深度（匹配字符个数）一定小于跳之前的节点。所以我们可以利用 bfs在 Trie上面进行每一层节点 ne指针的求解。

3.扫描主串进行匹配。

ne数组的定义是:
从a串跳到b串,b串一定是a的字串，那么那么b串一定也是a串某个前缀的后缀

treap 树 ： 二叉搜索树 + 堆 （ bst + heap)

说说这个BST，就是说一个根节点p，左儿子一定小于他，右儿子大于它。

也就是BST的中序遍历是严格单调递增的。

那么就可以进行一些操作了。

首先为了维护这个BST我们需要一个左旋zag和右旋zig，分别表示将根节点和左右儿子交换位置，使交换后还满足BST的性质。

但是有的时候BST会退化成一条链，时间复杂度就大大降低了，但是只要BST够随机，期望高度就是log n。

所以的话就把它和堆集合在了一起，变成了平衡树。