Trie 树进阶学习笔记
2024-09-03 00:08:28
前言
没脑子选手发现自己什么都不会 。。。
\(\text{More and more vegetables, What should I do?}\)
正文
Trie 树简介
大概是人类的话都知道吧,所以就不讲了 QWQ
Trie 树合并
定义:就是把两个 \(\text{Trie}\) 树进行合并的操作,并且合并维护的信息。
我们定义 int merge(int a, int b)
就是进行合并操作的函数。
\(a\) 和 \(b\) 分别是两个 \(\text{Trie}\) 树上的节点,最后返回值是合并完成的结点编号。
流程主要分成三个可能的情况:
- 如果 \(a\) 没有这个位置上的结点,新合并的结点就是 \(b\) 。
- 如果 \(b\) 没有这个位置上的结点,新合并的结点就是 \(a\) 。
- 如果 \(a,b\) 都存在,那就把 \(b\) 的信息合并到 \(a\) 上,新合并的结点就是 \(a\),然后递归操作处理 \(a\) 的左右儿子。
具体的话,看题目吧。
CF778C Trie合并模板
可持久化 Trie
主要思想:
就是说每次只修改被添加或值被修改的节点。
没有被改动的节点我们直接保留不加以修改。
并且在上一个版本的基础上连边。
使最后每个版本的 \(\text{Trie}\) 树的根遍历所能分离出的 \(\text{Trie}\) 树都是完整且包含全部信息的。
具体的代码是这样的:
inline int insert(int pre, int val) {
int now = ++tot, ret = now;
for (int i = 31; ~i; --i) {
int t = (val >> i) & 1;
son[now][t ^ 1] = son[pre][t ^ 1];
pre = son[pre][t];
now = son[now][t] = ++tot;
cnt[now] = cnt[pre] + 1;
}
return ret;
}
root[i] = insert(root[i - 1], b[i]);
具体的还是看题目而言吧。
最新文章
- List [][]
- jQuery-1.9.1源码分析系列(六) 延时对象
- rsync 通过 ssh 上传文件
- Groupby - collection processing
- 使用RESTClient插件进行数据模拟(GET,POST)提交
- c#ASP.NET中页面传值共有这么几种方式
- C# 跨线程操作控件(简洁)
- mongo 安装
- [HDOJ1698]Just a Hook(线段树,区间更新)
- C++11 lambda表达式学习
- Cocos2d-x 3.2 Lua演示样例 XMLHttpRequestTest(Http网络请求)
- eclipse配置虚拟路径后,每次启动tomcat都会虚拟路径失效的问题解决
- Linux之ulimit详解(整理)
- readonly 和 disabled的区别
- Linux配置防火墙端口 8080端口
- 史上最全面的Docker容器引擎使用教程
- 【题解】Luogu P2604 [ZJOI2010]网络扩容
- leetcode字符串系列
- webpack打包提取css到独立文件
- 12 extremely useful hacks for JavaScript