一.Trie树

1.存储

       Trie树是一种用于高效存储和查找字符串的数据结构。它有一个根节点，遇到一个字符时，首先查找根节点（或父节点）的子节点中有无该字符。若有，则往下走；若无，则创建。例如：

注意4的创建。首先对于b，它已经是根节点的一个子节点，无需重复创建；对于c同理。而对于f，c的已有子节点中没有f，故创建一个；对于p、o同理。一般来说，我们会在单词的结尾打上一个标记表示结束（图中星号）。
       代码实现：
注意，要理解下面两个数组的含义，我们必须先知道，在这个算法中，我们把a-z这26个字母依次映射到0-25这26个数字。那么，son[x1][x2]表示Trie树的第x1个父节点的x2位置的值（不管情况如何，我们总是给每个父节点都虚拟出26个子节点。如果该子节点的编号对应的字母确实是字符串中的下一个字母，那么就给该子节点赋值为++idx，否则为默认值0。那么到最后，son[x1][x2]的值如果是0，表示这一层没有出现x2对应的字母；若为非零，则出现了x2对应的字母），cnt[x3]表示以x3作为结尾编号的字符串条数，由于先后出现的相同字符串会有相同编号，因此它可以用于统计字符串条数。idx表示我们已经用到的下标，即：当前字母出现的位置顺序。如果先后插入相同的字符，例如cdm,ce,cdm，那么在第二次插入cdm时idx不会发生变化，当p往下走时最后会得到跟第一次插入cdm时最后p的值，那么cnt在相同的位置加一，就实现计算字符串的统计条数加一了。

const int N = 1e5+10;
int son[N][26],cnt[N],idx;void Insert(char str[])
{int p = 0;//从0开始向下走for(int i = 0;str[i];i++){int u = str[i] - 'a';//获取str[i]映射后的像if(!son[p][u])	son[p][u] = ++idx;p = son[p][u];}cnt[p]++;
}

2.查找

       比如说我们想查找abef，只需要从上往下遍历，找到结束的星号标志即可。若我们查找一个不存在的单词，例如mpsq，它一定会从某个节点开始找不到下一个节点。还有一种情况是查找的单词比已有的单词要短，例如bcee，那么虽然可以走到第二个e，但是第二个e处没有结束标志，所以这个单词不存在。
问题：既然我们已经一一检查给出的字符串的字母与已有字符串字母的吻合程度，为什么我们仍然需要cnt数组呢？这是为了控制长度。还是上面那个依次插入cdm,cpe,cdm的例子，如果不加cnt数组，那么当输入cd这个部分组，程序也会认为它出现过，但实际上这条字符串不存在！

int query(char str[])
{int p = 0;for(int i = 0;str[i];i++){int u = str[i] - 'a';//若son[p][u]=0，说明这个位置对应的字母没出现if(!son[p][u])	return 0;p = son[p][u];}return cnt[p];

二.并查集

       并查集支持快速实现以下两个操作：（1）判断两个元素是否属于同一个集合；（2）合并两个区间 。我们可以想想，这两个需求如何暴力实现呢？我们可以维护belong数组，它的第k个位置存储的是k元素属于的集合。那么对于一，只需要判断是否有belong[x] == belong[y]即可。但是对于（2），例如把新几何看作集合A的扩充，就必须要全部修改belong数组中原本是B的值，这样的时间复杂度是很大的。为了优化问题，我们可以利用并查集。我们用树去表示集合，树的根节点的编号就是该集合的编号。每个节点存储它的父节点的编号。图例如下：

问题1：如何判断某个节点是否为该树的根节点？
       假设我们用p数组存储x元素的父节点的值，我们可以在最开始将所有的节点存储的值赋为它自己。这样，若我们在最后还能遇到p[x] == x，那么就说明它是树根。
问题2：如何判断某个元素在不在集合里？如果在，如何求该元素的集合编号？
       只需要判断该元素在数组中对应的位置的值，一直往上推看看能否找到相应的根节点即可。伪代码为:：while(p[x] != x) x = p[x]。
问题3：如何合并两个集合？
       只要像上图中的红线那样，让某一个集合成为另一个集合的某个节点（一般我们选择另一个集合的根节点）的子节点就可以。若p[x] == x，p[y] == y，则令p[x] == y可完成合并。
       但是，在问题2解决方案中，时间复杂度还是较高的。我们如何优化呢？一旦我们某个节点找到了整棵树的根节点，那么就把它走过的路径上的所有节点都直接指向根节点。如图：

这样带来的好处是，假若我们后来还要查找一次以前查找过的某个元素在哪个集合，那么就可以一步到位。如此一来，时间复杂度就接近O（1）了。
注意，这里p[x]表示的是x的父节点的值而非编号！！因此，该算法要求不同集合中的元素不一样，否则有可能两个集合的根节点的值相同，但是它们的子节点并不属于同一个集合！这可能会带来判断错误！
下面是具体的代码实现：

#include
using namespace std;
const int N = 1e5+10;int n,m;
int p[N];int find(int x)
{//这里千万不能写成p[x] = find(x)！这样会陷入死递归！！一直出不来if(p[x]!=x)  p[x] = find(p[x]);return p[x];
}int main()
{scanf("%d%d",&n,&m);for(int i = 0;i<n;i++)  p[i] = i;while(m--){//这是一个好习惯，用字符串读字母。因为出题人可能在行末多加空格，那么scanf可能读取错误。而如果是读取字符串，就会自动忽略空格char op[2];int a,b;scanf("%s%d%d",op,&a,&b);if(op[0] == 'M')    p[find(a)] = find(b);else{if(find(a) == find(b))  printf("Yes\n");else    printf("No\n");}}
}

延伸

       这道题可以用并查集维护连通块。需求1、2跟前面的是一样的。而对于需求（3），我们需要额外开辟一个记录连通块中点的数目的数组，其中num[k]表示以k为根节点的连通块的点的数目。（我们约定，只有根节点处的num才有意义）。初始时，各个连通块只有一个点，所以我们把num的各个位置初始值赋成1就好。

#include
using namespace std;const int N = 1e5+10;
//size[k]表示k元素所在的连通块的点的个数。我们规定只有根节点的size是有意义的。
int p[N],num[N];int find(int x)
{if(p[x]!=x) p[x] = find(p[x]);return p[x];
}int main()
{int n,m;scanf("%d%d",&n,&m);for(int i = 0;i<n;i++){p[i] = i;num[i] = 1;}while(m--){char op[5];scanf("%s",op);if(op[0] == 'C'){int a,b;scanf("%d%d",&a,&b);//这里需要特判一下，如果find(a)==find(b)，即a与b已经在同一个连通块中，就不可以执行后面的操作了，否则连通块中的点的个数会计算到加倍。if(find(a)==find(b))    continue;//一定要先加等于再把连通块（集合）合并！否则会造成混乱。num[find(b)]+=num[find(a)];p[find(a)] = find(b);}else if(op[1] == '1'){int a,b;scanf("%d%d",&a,&b);if(find(a)==find(b))    printf("Yes\n");else    printf("No\n");}else{int a;scanf("%d",&a);printf("%d\n",num[find(a)]);}}return 0;
}

三、堆

       堆是一棵完全二叉树，其中小根堆指的是每个父节点都小于等于它的两个子节点的树，大根堆相反。那么我们可知，小根堆的根节点就是这个堆的最小值。

       堆有两个基本操作：向上调整和向下调整。后续的所有操作插入数据、求集合中的最小值、删除集合中的最小值、删除任意一个元素、修改任意一个元素都是它们的组合。下面我们以小根堆为例说明。

1.向下调整

       当我们把某个节点的值变大，根据定义，这时它的位置要下移。但是在下移的过程中我们不能破坏堆的结构，即仍然要保持父节点小于等于两个子节点。向下调整的过程中每层要与两个节点比较，找到三个点中的最小值，该最小值与改变的节点交换位置。

2.向上调整

       向上调整的过程中只需要和自己当前的父节点比较。如果比父节点都小，那么就肯定小于等于兄弟节点了。

3.具体操作（以下heap下标从1开始，这样可以保证2k为左儿子，2k+1为右儿子）

（1）插入数据
        把新的数据插入到堆的最后一个位置。假如我们用size表示堆的大小，x表示新数据，heap表示堆，那么伪代码为heap[++size] = x，然后再让从size处开始up，即up(size))。
（2）获取最小数
       就是heap[1]。
（3）删除最小值
       用整个堆的最后一个元素覆盖堆顶的元素，让size–，再down(1)就OK。
（4）删除任意一个元素
       比如要删除第k个位置的值，同样是让最后一个位置的值去覆盖它，即heap[k] = heap[size]，让size–然后再down（k)，up（k）即可。（因为无外乎是变大或者变小两种情况，若变小，会执行up；若变大，会执行down。这样虽然写了两个函数，但是只会执行一个，但可以避免分类讨论）
（5）修改任意一个元素
       比如要修改第k个位置的值，像上面一样的道理，heap[k] = x，up(k),down(k)即可（也是只会执行一个函数）。

问题:怎么建堆呢？我们当然可以采取一个一个数插入的方法，但这样做的时间复杂度是O（nlogn）。下面我们介绍一种O（n）的算法——向下调整。由于最后一层是最大的，不需要再down，而且最后一层约有n/2个元素，因此我们只需要从n/2开始往前down直到1即可。

#include
using namespace std;const int N = 1e5+10;int heap[N],num;void down(int k)
{//记录当前编号int t = k;//不要以为这里暂时有t = k就写heap[2*k]if(2*k<=num&&heap[2*k]<heap[t])     t = 2*k;//这个地方由于t已经被更新为2k，所以当右儿子存在时，它实际上是在与左儿子比较！！if(2*k+1<=num&&heap[2*k+1]<heap[t])    t = 2*k+1;if(k!=t){swap(heap[k],heap[t]);down(t);}
}int main()
{int n,m;scanf("%d%d",&n,&m);num = n;for(int i = 1;i<=n;i++){int x;scanf("%d",&x);heap[i] = x;}for(int i = n/2;i;i--)      down(i);while(m--){printf("%d ",heap[1]);heap[1] = heap[num];num--;down(1);}return 0;
}

下面我们实现up向上调整操作。

void up(int k)
{
//只要父节点存在并且比当前节点大就交换while(k/2>0&&heap[k/2]>h[k]){swap(heap[k/2],heap[k]);k/=2;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！