字典树与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;//记录每一个字符串的结束节点
}
//倍增求LCA
for (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;
}欧克了