字典树与01trie

news/2025/4/26 12:33:01/

字典树简介

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

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

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

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

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;
}

 欧克了

 

 


http://www.ppmy.cn/news/1583490.html

相关文章

【江协科技STM32】读写备份寄存器RTC实时时钟（学习笔记）

【江协科技STM32】读写备份寄存器RTC实时时钟（学习笔记）

参考相关文章理解&#xff1a; 【江协科技STM32】Unix时间戳&#xff08;学习笔记&#xff09;-CSDN博客 【江协科技STM32】BKP备寄存器&RTC实时时钟&#xff08;学习笔记&#xff09;_stm32断电保存时钟-CSDN博客 读写备份寄存器 接线图&#xff1a;VBAT是从STLINK的…
阅读更多...
三十而“砺”：百威“第一”工厂以创新驱动高质量增长

三十而“砺”：百威“第一”工厂以创新驱动高质量增长

&#xff08;2025年3月24日&#xff0c;中国武汉&#xff09;在中国外商投资企业协会双碳与可持续发展工作委员会、武汉外商投资企业协会、上海市外商投资协会的指导下&#xff0c;“三十而砺&#xff0c;源启未来”百威武汉工厂三十周年庆典暨世界水日活动在百威武汉工厂——百…
阅读更多...
Linux的进程信号 -- 信号产生，信号保存，信号捕捉，硬件中断，内核态和用户态，可重入函数，volatile，SIGCHLD

Linux的进程信号 -- 信号产生，信号保存，信号捕捉，硬件中断，内核态和用户态，可重入函数，volatile，SIGCHLD

目录 1. 认识信号 1.1 信号的定义和基本结论 1.1.1 查看信号 1.2 技术应用角度的信号 1.2.1 一个样例 1.2.2 系统调用 signal 函数 1.3 信号的处理 2. 信号的产生 2.1 通过终端按键产生信号 2.1.1 基本操作 2.1.2 理解操作系统如何得知键盘信号 2.1.3 初步理解信号…
阅读更多...
linux命令行工具进阶

linux命令行工具进阶

文章目录 前言ssh免密登录&#xff0c;免密码登录&#xff0c;公私钥查看与修改IP地址临时修改永久修改 mount临时切换根文件系统永久切换根文件系统loop文件partedinitramfsuboot command line 前言 本文记录了一些不经常用到&#xff0c;但在某个时刻需要用到的一些指令。 免…
阅读更多...
单表、多表查询练习

单表、多表查询练习

课堂练习代码&#xff1a; 一、单表查询 1、显示所有职工的基本信息。 mysql> select * from worker; --------------------------------------------------------------------------------- | 部门号 | 职工号 | 工作时间 | 工资 | 政治面貌 | 姓名 | …
阅读更多...
Python+Pytorch掌纹训练识别

Python+Pytorch掌纹训练识别

程序示例精选 PythonPytorch掌纹训练识别 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对《PythonPytorch掌纹训练识别》编写代码&#xff0c;代码整洁&#xff0c;规则&#xff0c;易读。 学…
阅读更多...
数据结构——顺序栈seq_stack

数据结构——顺序栈seq_stack

前言&#xff1a;大家好&#x1f60d;&#xff0c;本文主要介绍了数据结构——顺序栈 目录 一、概念 1.1 顺序栈的基本概念 1.2 顺序栈的存储结构 二、基本操作 2.1 结构体定义 2.2 初始化 2.3 判空 2.4 判满 2.5 扩容 2.6 插入 入栈 2.7 删除 出栈 2.8 获取栈顶元…
阅读更多...
算法 ｜ 小龙虾优化算法原理，引言，公式，算法改进综述，应用场景及matlab完整代码

算法 ｜ 小龙虾优化算法原理，引言，公式，算法改进综述，应用场景及matlab完整代码

小龙虾优化算法（Crayfish Optimization Algorithm, COA）详解 一、引言 背景与意义 小* 龙虾优化算法（COA）是一种受小龙虾自然行为启发的元启发式算法，模拟其温度适应、洞穴选择、觅食竞争等机制，用于解决复杂优化问题。相比传统算法（如遗传算法、粒子群优化），COA通过…
阅读更多...
最新文章

Copyright @ 2022~2023