数据结构
并查集
一种树形的数据结构，近乎O(1)的时间复杂度。
又一次理解了并查集用来维护额外信息的作用，可以用来记录集合中的元素个数，也可以维护节点到根节点之间的距离，可能还有别的，然后在进行路径压缩的时候修改需要维护
的额外信息。
主要构成 pre[]数组、find()、join()
1.可以将两个集合合并
2.询问两个元素是否在一个集合当中
//pre数组初始化
void Init(int n){
//每个结点的祖先都是自己
for(int i=0;i<n;i++){
pre[i]=i;
}
}
//pre[x]中存放的是x结点的父节点
//find()函数找到某个结点的根，结点的祖先
int find(int x) //查找某个结点的父节点
{
while(pre[x] != x)
x = pre[x];
return x;
}
find()函数优化：路径压缩。就是将所有结点的父节点都改为根结点，这样子查找某个结点的父节点只需要向上查找一次
int find(int x) //查找结点 x的根结点
{
if(pre[x]!=x)pre[x]=find(pre[x]);//如果没有找到根节点，就把每一个根节点都赋值给集合中的节点
return pre[x];//最后返回的时候，每个节点的根节点都会改成同一个值（根节点）。
}
//将两个集合合并
void join(int x,int y)
{
//找到各自的父节点
int fx=find(x);
int fy=find(y);
//将fy和fx其中任意一个作为根
if(fy!=fx)
pre[fy]=fx;
}
并查集的使用：
- 在一个图中，给出询问判断两点之间是否可以到达，利用bfs或dfs是一种方式，但是这种方式对于多组询问时时间复杂度太高了，可以通过构造并查集，位于同一个集合中的点可以互相到达，查询的时间复杂度可以做到O(1)。
Trie（字典树）
Trie，又称字典树或前缀树，常用来存储和查询字符串。假定接下来提到的字符串均由小写字母构成，那么Trie将是一棵 26 叉树。
Trie存二进制数据或存字符串（以下代码为存二进制数）
ll a[N];//原始数据
ll son[M][2];//存Trie树
int idx;//Trie树结点下标
//插入Trie树
//插入的步骤一般不会有变化，就是可能会增加cnt数组来维护字典树的额外信息，比如说经过某个结点的数的个数或者某个数出现的次数。
void insert(int x){
int p=0;//树指针
for(int i=30;i>=0;i--){
int t=(x >> i) & 1;//获得最高位
if(!son[p][t]) son[p][t]=++idx;//son[p][t]=0表示根结点没有值为“t”的子结点
p=son[p][t];
}
}
//查询某个数
//查询就是遍历已经存在的字典树，完成相应的处理，比如说找到最大异或对，或者判断字符串是否已经出现过
ll query(int x){
int p=0;
ll res=0;
for(int i=30;i>=0;i--){
int t=(x>>i)&1;
if(son[p][1-t]){
res+=(1<<i);
p=son[p][1-t];
}else{
p=son[p][t];
}
}
return res;
}
树状数组
树状数组本质上就是利用树结构来维护“前缀和”，从而把区间查询的时间复杂度降为O(logn)。
修改时间复杂度O(logn)，计算前缀和之间复杂度O(logn)。
注意：
- 单点修改，区间查询。t数组相当于是一个前缀和数组，求和就表示区间的和
- 区间修改，单点查询，t数组相当于是一个差分数组，差分数组求和就表示求解序列中某个元素的值。
对一个序列建立如下所示的树形结构：
-
每个结点t[x]保存以x为根的子树中叶结点值的和（也就是前缀和1~i中的一部分的和），在计算前缀和时需要多个t数组相加
如计算sum[7]=t[7]+t[6]+t[4];
-
每个结点覆盖的长度为lowbit(x)（lowbit(x)：非负整数x在二进制表示下最低位1以及后面的0构成的数值）
-
t[x]结点的父结点为t[x + lowbit(x)]
-
树的深度为log2n+1
int lowbit(int x){
//一个数取反+1=一个数取负
return x&-x;
}
//单点修改，t数组为前缀和数组
void add(int x,int k){
//每次修改序列中的一个元素的值时，该元素所在的到根节点的路径上的t[]都需要改变
for(int i=x;i<=n;i+=lowbit(i)){
t[i]+=k;
}
}
//区间修改，t数组为差分数组，需要修改两个子树的值
void add(int l,int r,LL k){
for(int i=l;i<=n;i+=lowbit(i)){
t[i]+=k;
}
for(int i=r+1;i<=n;i+=lowbit(i)){
t[i]-=k;
}
}
//计算前缀和
int sum(int x){
int res=0;
for(int i=x;i>0;i-=lowbit(i)){
res+=t[i];
}
return res;
}
线段树
注意：1 .对于区间修改问题利用线段树来做的时候，首先要确定线段树维护的是怎样的一个区间(一般都是题目需要求解的答案)，对于区间的修改的时间复杂度一般为O(1)，因为树的搜索的时间复杂度为O(logn)，一般有O(n)的询问和修改区间的复杂度，最终复杂为O(nlogn)。2.单点修改不需要设置懒标记，区间修改的时候需要设置懒标记。3.一般线段树的数组大小是4倍的节点数量(4*N)
线段树流程(以加乘线段树为例)：
- 建立线段树，通过递归的方式建立，当l==r时表示到达叶子节点
- 进行区间修改，递归的边界条件是找到一棵子树的管辖区间是目标区间的子集，就可以停止向下寻找，并在这棵子树的根节点进行区间修改（此时只是修改了根节点，根节点的孩子还未修改），然后对根节点添加懒标记。在不满足边界条件的区间，如果碰到了有懒标记的节点，就将这个懒标记下发给它的左孩子和有孩子，并将该节点的懒标记清空，该操作就是pushdown函数。
/*
区间修改！！
区间需要懒标记，而单点修改不需要懒标记，找到满足的单点直接修改就可以了
*/
LL a[N],d[M],mul[M],add[M];//mul乘法懒标记，add加法懒标记
//创建线段树
void build(LL l,LL r,int p){
mul[p]=1;//初始化乘法懒标记
if(l==r){
d[p]=a[l];
return;
}
LL mid=l+(r-l)/2;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
d[p]=(d[p*2]+d[p*2+1])%mod;
}
//下压懒标记
void pushdown(LL s,LL t,int p){
//将父节点的懒标记下移到子节点，先乘后加
LL mid=s+(t-s)/2;
d[p*2]=(d[p*2]*mul[p]+add[p]*(mid-s+1))%mod;
d[p*2+1]=(d[p*2+1]*mul[p]+add[p]*(t-mid))%mod;
//乘法懒标记
mul[p*2]*=mul[p],mul[p*2]%=mod;
mul[p*2+1]*=mul[p],mul[p*2+1]%=mod;
//加法懒标记，先记住这个计算公式
add[p*2]=(add[p*2]*mul[p]+add[p])%mod;
add[p*2+1]=(add[p*2+1]*mul[p]+add[p])%mod;
add[p]=0,mul[p]=1;
}
//区间乘
void range_mul(LL l,LL r,LL k,LL s,LL t,int p){
if(l<=s && t<=r){
d[p]=(d[p]*k)%mod;
mul[p]*=k,mul[p]%=mod;
//这里还不是很理解，不知道为什么也要同时修改加法懒标记
add[p]*=k,add[p]%=mod;
return;
}
LL mid=s+(t-s)/2;
//下压标记
pushdown(s,t,p);
if(mid>=l) range_mul(l,r,k,s,mid,p*2);
if(mid<r) range_mul(l,r,k,mid+1,t,p*2+1);
d[p]=(d[p*2]+d[p*2+1])%mod;
}
//区间加
void range_add(LL l,LL r,LL k,LL s,LL t,int p) {
LL mid=s+(t-s)/2;
//找到区间的子集，直接修改这个节点，不继续向下修改，并添加懒标记
if(l<=s && t<=r){
d[p]+=k*(t-s+1),d[p]%=mod;
add[p]+=k,add[p]%=mod;
return;
}
pushdown(s,t,p);
if(mid>=l) range_add(l,r,k,s,mid,p*2);
if(mid<r) range_add(l,r,k,mid+1,t,p*2+1);
//回溯更新上面的节点
d[p]=(d[p*2]+d[p*2+1])%mod;
}
//区间求和
LL get_sum(LL l,LL r,LL s,LL t,int p){
LL mid=s+(t-s)/2;
if(l<=s && t<=r){
return d[p];
}
//在搜索的路上下压懒标记
pushdown(s,t,p);
LL sum=0;
if(mid>=l) sum+=get_sum(l,r,s,mid,p*2),sum%=mod;
if(mid<r) sum+=get_sum(l,r,mid+1,t,p*2+1),sum%=mod;
return sum;
}
数组模拟单链表
int e[N],ne[N],idx,head=-1;//head为链表的头指针
memset(ne,-1,sizeof ne);//需要对ne数组进行初始化，-1表示指向null
void insert(int x){
e[idx]=x;//存的数据
ne[idx]=head;//模拟指针，指向下一个数据
head=idx++;
}
//删除第k个数据,其实删除并没有真正的删除，而是通过修改ne数组（指针指向）来达到删除的目的
void del(int k){
ne[k]=ne[ne[k]];
}
//遍历链表
void showList(){
for(int i=head;i!=-1;i=ne[i]){
//打印语句
}
}
单调栈
单点栈和单调队列类似，但是单调栈只在一端进出。
应用： 找到前一个比它还大（小）的数、找到后一个比它还大（小）的数。以找到前一个比它还小的数为例，需要维护一个单调递增栈，
如果>=栈顶就一直出栈，最后满足条件的就是第一个比它小的数。注意： 如果找后一个比他还大（小）的数，序列需要从后往前遍历。
//找到左边第一个比a[i]小的数，相当于维护一个不减单调栈
for(int i=0;i<n;i++){
while(hh<=tt && a[stack[tt]]>=a[i])tt--;
if(hh<=tt){
l[i]=stack[tt];
}else l[i]=-1;//注意边界的设置
stack[++tt]=i;//入栈
}
单调队列
单调队列一般适用于求解一段区间内的最大或最小值（一维滑动窗口问题）。
//模拟队列
int q[N];
int hh=0,tt=-1;
q[++tt]=x;//入队
hh++;//出队
q[hh];//访问队头元素
hh<=tt;//表示队列不为空
//模拟栈
int stk[N];
int tt=-1;
stk[++tt]=x;//压栈
tt--;//出栈
stk[tt];//访问栈顶
tt>=0;//表示栈不为空
//一维滑动窗口求解
//求解某个序列中k范围内的极小值
void get_min(int a[],int f[],int len){
//f用来存下k范围内的极值
int hh=0,tt=-1;
for(int i=1;i<=len;i++){
while(hh<=tt && i-que[hh]+1>k)hh++;
while(hh<=tt && a[i]<=a[que[tt]])tt--;
que[++tt]=i;
f[i]=a[que[hh]];//没有加判断，表示<=k也是合法的，
}
}
//求解某个序列k范围内的极大值
void get_max(int a[],int f[],int len){
int hh=0,tt=-1;
for(int i=1;i<=len;i++){
while(hh<=tt && i-que[hh]+1>k)hh++;
while(hh<=tt && a[i]>=a[que[tt]])tt--;
que[++tt]=i;
f[i]=a[que[hh]];
}
}
二维滑动窗口问题
先求出每一行的极值，然后在这么多行的极值中再取极值，这样的结果就是区间中的极值了。
我们要求解的是一个矩阵中的极值。我们可以把它转化为一维的问题，首先求出每一行中区间内的极值，然后再对不同行的同一列的的极值再一次求解多个极值中的极值。这样就能求出区间中的极值。
//求解每一行的最小值
for(int i=1;i<=n;i++){
get_min(a[i],min_row[i],m);//第i行区间内的最小值存在minv_row[i]，有m为区间长度
get_max(a[i],max_row[i],m);
}
//求解n行中同一列的最小值，也就是区间最小值
int res=1e9;
//对每一列进行判断
for(int i=k;i<=m;i++){
//先把某列的值取出来
for(int j=1;j<=n;j++){
min_col[j]=min_row[j][i];
max_col[j]=max_row[j][i];
}
//求解某列的最小极差
get_min(min_col,res_min,n);
get_max(max_col,res_max,n);
for(int j=k;j<=n;j++) res=min(res,res_max[j]-res_min[j]);//求解极差
}
邻接表
int h[N],e[M],w[M],ne[M],idx;//idx为边的序号
void add(int a, int b, int c) // 添加有向边 u->v, 权重为weight
{
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;//头插法
}
模拟散列表
拉链法：
const int N=1e5+10;
int h[N],e[N],ne[N],idx;
//拉链法
void insert(int x){
int k=(x%N+N)%N;
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
//查询
bool query(int x){
int k=(x%N+N)%N;
for(int i=h[k];~i;i=ne[i]){
if(e[i]==x)return true;
}
return false;
}
开放寻址法：
const int N=2e5+10,INF=0x3f3f3f3f;
int h[N];
//开放寻址法
void insert(int x){
int k=(x%N+N)%N;
while(h[k]!=INF){
k++;
if(k==N) k=0;
}
h[k]=x;
}
//查询
bool query(int x){
int k=(x%N+N)%N;
int t=k;
while(h[k]!=x && h[k]!=INF){
k++;
if(k==N)k=0;
if(k==t)break;
}
if(h[k]==x)return true;
else return false;
}