Trie树：用来高效存储和查找字符串集合的数据结构：

模板题：https://www.acwing.com/problem/content/837/

AC代码：

#include<bits/stdc++.h>
using namespace std;
int son[100010][26],cnt[100010],idx;
char str[100010];
void insert(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];}cnt[p]++;
}
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;cin>>n;while (n -- ){char op[2];scanf("%s%s",op,str);if(op[0]=='I') insert(str);else printf("%d\n",query(str));}
}

再来个十分典的：https://www.acwing.com/problem/content/145/

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int son[3200000][2],idx,a[100010];
int n;
void insert(int k)
{int p=0;int res=0;for(int i=30;i>=0;i--){int u=k>>i&1;if(!son[p][u]) son[p][u]=++idx;p=son[p][u];}
}
int query(int k)
{int p=0,res=0;for(int i=30;i>=0;i--){int u=k>>i&1;if(!son[p][1-u]){p=son[p][u];res=2*res+u;}else{p=son[p][1-u];res=2*res+1-u;}}return res;
}
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int res=0;for(int i=1;i<=n;i++){insert(a[i]);int ck=query(a[i]);res=max(res,a[i]^ck);}cout<<res;
}

堆：

主要实现这5个功能：

1.插入一个数 2.求集合最小值 3.删除最小值 4.删除任意一个元素 5.修改任意一个元素

是一个完全二叉树，对于小根堆每一个父节点小于它的儿子，根节点就是min

模板题：https://www.acwing.com/problem/content/840/

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int h[100010],size1;
void down(int u)
{int t=u;if(u*2<=size1&&h[u*2]<h[t]) t=u*2;if(u*2+1<=size1&&h[u*2+1]<h[t]) t=u*2+1;if(u!=t){swap(h[u],h[t]);down(t);}
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>h[i];size1=n;for(int i=size1/2;i;i--) down(i);while (m -- ){cout<<h[1]<<" ";h[1]=h[size1];size1--;down(1);}
}

模板题：https://www.acwing.com/problem/content/841/

其中用到了映射关系，具体可以看某大佬题解：https://www.acwing.com/solution/content/5661/

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5+10;
int h[N];   //堆
int ph[N];  //存放第k个插入点的下标
int hp[N];  //存放堆中点的插入次序
int cur_size;   //size 记录的是堆当前的数据多少
void heap_swap(int u,int v)
{swap(h[u],h[v]);swap(ph[hp[u]],ph[hp[v]]);swap(hp[u],hp[v]);
}void down(int u)
{int t=u;if(u*2<=cur_size&&h[t]>h[u*2]) t=u*2;if(u*2+1<=cur_size&&h[t]>h[u*2+1])  t=u*2+1;if(u!=t){heap_swap(u,t);down(t);}
}
void up(int u)
{if(u/2>0&&h[u]<h[u/2]) {heap_swap(u,u/2);up(u>>1);}
}
int main()
{int n,m=0;cin>>n;while (n -- ){string op;int k,x;cin>>op;if(op=="I"){cin>>x;m++;h[++cur_size]=x;ph[m]=cur_size;hp[cur_size]=m;up(cur_size);down(cur_size);}else if(op=="PM")    cout<<h[1]<<endl;else if(op=="DM"){heap_swap(1,cur_size);cur_size--;down(1);}else if(op=="D"){cin>>k;int u=ph[k];//注意不能直接ph[k]heap_swap(ph[k],cur_size);cur_size--;down(u);up(u);}else if(op=="C"){cin>>k>>x;h[ph[k]]=x;                 down(ph[k]);                up(ph[k]);}}
}

哈希表：按照存储结构可以分为开放寻址法以及拉链法

模板题：https://www.acwing.com/problem/content/842/

拉链法的AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100003,null=0x3f3f3f3f;//最好是质数
int h[N],e[N],ne[N],idx;//链表,h相当于槽,类似链式前向星
void insert(int x){int k=(x%N+N)%N;e[idx]=x,ne[idx]=h[k],h[k]=idx++;}
bool find(int x){int k=(x%N+N)%N;for(int i=h[k];i!=-1;i=ne[i]){if(e[i]==x) return 1;}return 0;
}
int main(){int n;cin>>n;memset(h,-1,sizeof(h));while(n--){char op[2];int x;scanf("%s%d",op,&x);if(*op=='I') insert(x);else{if(find(x)) puts("Yes");else puts("No");}}
}

开放寻址法：

#include<bits/stdc++.h>
using namespace std;
const int M=200003,null=0x3f3f3f3f;
int h[M];
int find(int x){int k=(x%M+M)%M;while(h[k]!=null&&h[k]!=x){k++;if(k==M) k=0;}return k;
}
int main(){int n;cin>>n;memset(h,0x3f,sizeof(h));while(n--){char op[2];int x;scanf("%s%d",op,&x);if(*op=='I'){int k=find(x);h[k]=x;}else{int k=find(x);if(h[k]!=null) puts("Yes");else puts("No");}}
}

还可以通过字符串前缀哈希法：https://www.acwing.com/activity/content/problem/content/891/

具体就是先确定一个把字符串映射成一个数的函数，我们可以把它看出p进制再mod Q，A,B,等赋予不同的权值（最好不要0，否则AA,A就是同一个了），这里有个经验值，我们一般取p=131或者13331,Q=2^64,我们可以认为此时没有冲突值。

这样+前缀哈希就可以计算出所有子串的哈希值：h[r]-h[l]*p^(r-l+1).

这里有个技巧：我们开unsigned long long 这样modQ就可以用溢出直接代替了 

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 100010, P = 131;int n, m;
char str[N];
ull h[N], p[N];
ull get(int l, int r)
{return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{scanf("%d%d", &n, &m);scanf("%s", str + 1);p[0]=1;for(int i=1;i<=n;i++){h[i] = h[i - 1] * P + str[i];p[i] = p[i - 1] * P;}while (m -- ){int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);if (get(l1, r1) == get(l2, r2)) puts("Yes");else puts("No");}
}