写在最前面：

此系列中的所有模板全为大佬所写，我只是一个搬运工（？）。

本次算法均为用数组模拟STL，这样的速度更快而且可操作性更强。

记录

Trie树

高效的存储和查找字符串的数据结构。一般都会限制字符串的内容，比如大写字母，小写字母，或者数字。诸如此类的。最上方为根节点，在每个字符串最后有结尾标记。大概模型如下图。 alt

一般解决方案：

插入字符串：如果原来的树里面没有该字符串的开头字符的话，则新开一支来记录该字符串，如果有该字符，则直接在该字符下面继续查找有无待插入字符串的字符，然后重复以上操作。最后记录字符串末尾所在的位置。
查找字符串：与插入字符串类似，只不过在没有相同字符的时候直接返回无搜索结果即可。如果待查找字符全部查到并且结束字符有结束标记，则查找成功，返回一共相同的字符串个数。（如果字符串不相同那么不会结束在同一字符上，即树在延伸出去之后不会再返回。）

下面是模板：

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+10;
int son[N][26];//本题限定的是小写字母，所以每个字母延伸出来的枝条最多有26条
int cnt[N];//以当前节点为结尾的字符串由多少个
int idx=0;//下标是0的点，既是根节点又是空节点
char str[N];
void insertd(char *str)
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];//p是结尾字符的编号
    }
    cnt[p]++;//以该字符为结尾的字符串+1
}
int query(char *str)
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if((!son[p][u])) return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    scanf("%d",&n);
    while (n--)
    {
        char op[2];//存储技巧，可以用这个匹配掉前面多余的空格
        scanf("%s%s",op,str);
        if(op[0]=='I')insertd(str);
        else printf("%d\n",query(str));
    }
    return 0;
}

并查集

主要作用有两个：

将两个集合合并。
询问两个元素是否在同一个集合中。

原理： 每个集合都用一棵树表示，树根的编号就是集合的编号。

这里用p[x]表示x的父节点。

基本操作：

优化路径压缩： 把遍历过一次的子节点全部指向根节点，减少查询次数。
如何判断根节点：p[x]和x相等。
合并集合x和y：x做y的子节点或者y做x的子节点。（图中是y做x的子节点）
如果要求算一个集合有多少个子节点，可以在父节点记录一共有多少子节点，如果合并直接把两个父节点的子节点数量相加。同时，只有父节点的计数才有意义。

下面是模板：

 #include <iostream>
#include <cstdio>
const int N=1e5+10;

using namespace std;
int m,n;
int ssize[N];//算一个集合有多少个数字，只保证一个数的根节点有意义
int p[N];
int ffind(int x)//路径压缩
{
    if(p[x]!=x) p[x]=ffind(p[x]);//如果不是根节点，那么就递归找根节点
    return p[x];
}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<n+1;i++) p[i]=i,ssize[i]=1;//最开始每个数在各自的集合中

    while (m--)
    {
        char op[2];//使用字符管可以过滤掉前面的空格回车直接读有用的字符
        int a,b;
        scanf("%s%d%d",op,&a,&b);

        if(op[0]=='M')
        {
            p[ffind(a)]=ffind(b);//把一个的父节点作为另外一个的子节点。
            if(ffind(a)==ffind(b)) continue;//根节点相同就直接继续
            ssize[ffind(b)]+=ssize[ffind(a)];//把a节点的集合数加入进b中
        }
        else
        {
            if(ffind(a)==ffind(b)) puts("Yes");
            else puts("No");//自带回车
        }
    }
    return 0;
}

堆（优先序列）

维护一个数据集。表现形式为完全二叉树，从上到下依次排满，最低一层从左到右依次排满。而小根堆即为所有子节点都比父节点大。

用一维数组存储堆的方法：从i=1开始，然后左子节点为2 * i，右节点为2 * i = 1. alt

基本操作：（用heap[N]表示小分堆）

插入一个数（一般加到堆尾）
求集合里的最小值（堆顶）
删除最小值（删除堆顶，即用堆尾覆盖堆顶，再做调整）
删除任意一个元素（删除该元素，即用堆尾覆盖该元素，再做调整）
修改任意一个元素（直接覆盖该元素，再做调整）

核心操作：

up：数字小的向堆顶移动。直接和其父节点作比较，小则移动，大则不变。
down：数字大的下沉。父节点和两个子节点作比较，如果子节点小于父节点，则父节点和最小的子节点交换位置，否则不变。

下面是模板：

#include <iostream>
#include <cstdio>
const int N=1e5;

using namespace std;
int n,m;
int h[N];//heap堆
int num=0;//堆里面的数字个数

void down(int x)//把x下降进子节点
{
    int t=x;
    if(x*2<=num&&h[x*2]<x) t=x*2;
    if(x*2+1<=num&&h[x*2+1]<x) t=x*2+1;

    if(x!=t)
    {
       swap(h[x],h[t]);
       down(t);
    }
}

void up(int x)
{
    while(x/2&&h[x/2]>h[x])//u/2>0存在而且父节点比子节点大
    {
        swap(h[x],h[x/2]);
        x/=2;
    }
}
int main()
{
     scanf("%d%d",&n,&m);
    for(int i=1;i<n+1;i++) scanf("%d",&h[i]);
    num=n;

    for(int i=1;i<n/2;i++) down(i);//堆的初始化，从倒数第二行开始判断是否要做down操作。

    //删除最小值（用最后一个值覆盖掉最小值h[1]）
    h[1]=h[num];
    down(1),up(1);//不用判断大小，直接都做一遍一步到位就加上up（1）
    num--;

    int k;
    scanf("%d",&k);
    //删除第k个节点
    h[k]=h[num];
    num--;
    down(k);

    //把第k个数字换成x
    int x;
    scanf("%d",&x);
    h[k]=x;
    down(k);


    return 0;
}

【算法】Trie树、并查集、堆

写在最前面：

记录

Trie树

一般解决方案：

并查集

基本操作：

堆（优先序列）