字典树与01trie

字典树简介

当我们通过字典查一个字或单词的时候，我们会通过前缀或关键字的来快速定位一个字的位置，进行快速查找。

字典树就是类似字典中索引表的一种数据结构，能够帮助我们快速定位一个字符串的位置。

字典树是一种存储字符串的数据结构，除了根节点，每个节点可以存储一个字符，从根节点到树上某一结点的路径代表一个字符串

在向字典树中添加字符串的时候，如果一个字符串在某个节点结束，我们可以给这个节点打上一个标记。这样在后续访问时就可以知道到此节点为止为以一个完成的字符串。

const int N=1e5+10;
//第一维表示节点标号，第二维表示该节点到下一节点
int nxt[N][26];
//标记数组
bool isend[N];
//根节点和树的元素个数
int root=0,cnt=0;

字典树的插入

void insert(char s[],int len)
{int now=0;for(int i=1;i<=len;i++){int x=s[i]-'a';if(!nxt[now][x])nxt[now][x]=++cnt;//当原树中不存在这一条路径时，添加节点，创建路径now=nxt[now][x];}isend[now]=true;
}

 字典树的查找

bool search(char s[],int len)
{int now=0;for(int i=1;i<=len;i++){int x=s[i]-'a';if(!nxt[now][x])return false;now=nxt[now][x];}return isend[now];
}

 字典树的删除的情况比较少见

这时候我们要记录每个数节点的子树大小，这里的子树大小是指在这个节点下有几个真实存在的字符串。

对于要删除的字符串，先用查找字符串的方式找到该字符串在字典树中的最后一个节点，删除标记，然后回溯整条路径，如果路径上节点的子树大小为零，就可以删除这个节点

//删除操作需要有一个e数组
//e[x],表示的是经过x节点有几个字符串
//在删除操作时，需要将该字符串经过的路径e[x]--
//当发现该节点e[x]为1时，就说明只有这一条字符串经过该路径，将此节点删除，就将该字符串成功删除
int e[N]
void insert(char s[],int len)
{int now=0;e[now]++;for(int i=1;i<=len;i++){int x=s[i]-'a';if(!nxt[now][x])nxt[now][x]=++cnt;now=nxt[now][x];e[now]++;}isend[now]=true;
}
void remove(char s[],int len)
{int now=0;e[now]--;for(int i=1;i<=len;i++){int x=s[i]-'a';int tmp=nxt[now][x];if(e[tmp]==1)e[now][x]=0;//删除操作now=tmp;e[tmp]--;}isend[now]=false;
}

写一道例题蓝桥3755小蓝的神秘图书馆

 

 

ac代码如下

#include<iostream>
using namespace std;
using ll = long long;
const int N = 5e5 + 5;
int nxt[N][26];
ll e[N];
int cnt = 0;
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, m; cin >> n >> m;for (int i = 1; i <= n; i++){string str; cin >> str;int len = str.length();int now = 0;e[now]++;for (int j = 0; j < len; j++){int x = str[j] - 'a';if (!nxt[now][x]){nxt[now][x] = ++cnt;}now = nxt[now][x];++e[now];}}while (m--){string str; cin >> str;int len = str.length();int now = 0;bool flag = true;for (int j = 0; j < len && flag; j++){int x = str[j] - 'a';if (!nxt[now][x]){flag = false;}else now = nxt[now][x];}if (flag){cout <<e[now] << endl;}else cout << 0 << endl;}return 0;
}

 字典树除了可以对字符串进行前缀判定，还可以对字符串进行排序

原理就是既然字典树是一颗树，那我们就可以以遍历树的方式来遍历字典树，字典树的每一节点都有26条向下的边(当然大部分边是不存在的)我们优先往小的字典序遍历，进行一次dfs就可以对所有的字符串进行排序了

上例题

 代码如下

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
using namespace std;
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int N = 1e5 + 10;
int nxt[N][26];
int cnt = 0,n;
bool isend[N];
int str[30];
void dfs(int x, int deep)
{if (isend[x]){for (int i = 1; i <= deep; i++)cout << (char)(str[i]+'a');cout << endl;}for (int i = 0; i < 26; i++){if (nxt[x][i]){str[deep + 1] = i;dfs(nxt[x][i], deep + 1);}}
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++){string s; cin >> s;int len = s.length();int now = 0;for (int j = 0; j < len; j++){int x = s[j] - 'a';if (!nxt[now][x])nxt[now][x] = ++cnt;now = nxt[now][x];}isend[now] = true;}dfs(0, 0);return 0;
}

最后可以用字典树来求解最长公共前缀问题

 

以树的方式来看这个问题，求任意两个字符串的最长公共前缀，其实就是求解两个节点的最近公共祖先，那就得到了最长公共前缀

求解LCA问题，依旧可以使用倍增的思想

代码如下

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
using namespace std;
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int N = 1e5 + 10;
int nxt[N][26];
int cnt = 0,n,m;
int ed[N],fa[N][30];
int d[N];
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++){string s; cin >> s;int len = s.length();int now = 0;for (int j = 0; j < len; j++){int x = s[j] - 'a';if (!nxt[now][x]){nxt[now][x] = ++cnt;fa[cnt][0] = now;d[cnt] = d[now] + 1;//记录深度}now = nxt[now][x];}ed[i] = now;//记录每一个字符串的结束节点}//倍增求LCAfor (int i = 1; i <= 20; i++){for (int j = 1; j <= cnt; j++){if (fa[j][i - 1]){fa[j][i] = fa[fa[j][i - 1]][i - 1];}}}cin >> m;while (m--){int x, y; cin >> x >> y;x = ed[x], y = ed[y];if (d[x] < d[y])swap(x, y);int z = d[x] - d[y];for (int i = 0; i <= 20&&z; i++, z >>= 1){if (z & 1)x = fa[x][i];}if (x == y){cout << d[x] << endl;continue;}for (int i = 20; i >= 0; i--){if (fa[x][i] != fa[y][i]){x = fa[x][i];y = fa[y][i];}}cout << d[fa[x][0]] << endl;}return 0;
}

 接下来是01trie

01trie是一种二叉树，每一个叶子节点对应一个二进制数，通过从根出发到该节点的路径表示，深度小的表示二进制高位

01trie通常用于解决最大异或对问题，即求解a[i]^a[j]的最大值的问题

01trie支持三种操作

1.插入元素x

2.查询01trie中与x异或后最大的元素

3.查询比x更大的元素个数，可用于解决逆序对问题

还可以结合二分等算法实现更多操作

这样就可以创建一个01trie，与字典树几乎一样

01trie的插入

void insert(int x)
{int now=1;e[now]++;for(int i=30;i>=0;i--){  int y=(x>>i)&1;if(!nxt[now][y])nxt[now][y]=++cnt;now=nxt[now][y];e[now]++;}
}

01trie的查询

//查询01trie中与x异或的最大值
int query(int x)
{int now=1;int res=0;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(nxt[now][!y])now=nxt[now][!y],res+=(1<<i);else now=nxt[now][y];}return res;
}
//查询01trie中比x大的数目
int query(int x)
{int res=0;int now=1;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(y==0)res+=e[nxt[now][1]);if(!nxt[now][y])break;now=nxt[now][y];}return res;
}

 下面来写一道例题蓝桥17205卓儿的最大异或和

考虑异或的性质，将前缀异或添加到字典树中，每次询问求与当前前缀异或的最大值，就可以询问到每一个区间，每次取max就能得到答案

ac代码如下

#include<iostream>
using namespace std;
using ll=long long;
const int N=32*1e5+10;
int nxt[N][2];
int n,cnt=1;
ll pre[N];
void insert(int x)
{int now=1;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(!nxt[now][y])nxt[now][y]=++cnt;now=nxt[now][y];}
}
ll query(ll x)
{int now=1;ll res=0;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(nxt[now][!y])now=nxt[now][!y],res+=(1ll<<i);else now=nxt[now][y];}return res;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n;int x;ll ans=-1;insert(0);for(int i=1;i<=n;i++){cin>>x;pre[i]=pre[i-1]^x;ans=max(ans,query(pre[i]));insert(pre[i]);}cout<<ans<<endl;
}

 接下来是关于01trie删点求最大异或

蓝桥19721最大异或和

考虑枚举每一个节点，然后删除与它相邻的节点，求一次最大异或和，再将点添加回去

ac代码如下

#include<iostream>
#include<vector>
using namespace std;
const int N=32*1e5+5;
int nxt[N][2];
int e[N];
int n,cnt=1;
void insert(int x)
{int now=1;e[now]++;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(!nxt[now][y])nxt[now][y]=++cnt;now=nxt[now][y];e[now]++;}
}
void remove(int x)
{int now=1;e[now]--;for(int i=30;i>=0;i--){int y=(x>>i)&1;now=nxt[now][y];e[now]--;}
}
int query(int x)
{int res=0;int now=1;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(nxt[now][!y]&&e[nxt[now][!y]])now=nxt[now][!y],res|=(1<<i);else now=nxt[now][y];}return res;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;vector<int>a(n+1);vector<vector<int>> p(n+1,vector<int>());for(int i=1;i<=n;i++){cin>>a[i];insert(a[i]);}for(int i=1;i<=n;i++){int x;cin>>x;if(x!=-1){p[x+1].push_back(i);p[i].push_back(x+1);}}int ans=0;for(int i=1;i<=n;i++){for(auto y:p[i])remove(a[y]);ans=max(ans,query(a[i]));for(auto y:p[i])insert(a[y]);}cout<<ans<<endl;
}

最后来用01trie求逆序对

 

建树，然后就求出来了

#include<iostream>
#include<vector>
using namespace std;
using ll=long long;
const int N=32*1e5+10;
int nxt[N][2],e[N],n,cnt=1;
void insert(int x)
{int now=1;e[now]++;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(!nxt[now][y])nxt[now][y]=++cnt;now=nxt[now][y];e[now]++;}
}
int query(int x)
{int now=1;int res=0;for(int i=30;i>=0;i--){int y=(x>>i)&1;if(y==0)res+=e[nxt[now][1]];if(!nxt[now][y])break;now=nxt[now][y];}return res;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;ll ans=0;for(int i=1;i<=n;i++){int x;cin>>x;insert(x);ans+=query(x);}cout<<ans<<endl;
}

 欧克了