【学习笔记】压位 Trie
Unnamed114514
·
·
算法·理论
推荐阅读
板子链接
事实上，压位 Trie 已经算一个比较偏的知识点了，便得 OI-wiki 上都没有。在实际应用中，除了不完全优化掉一个 \log 之外没有任何用处。
引入
首先，板子的操作可以规约为以下问题：
有一个比较 ez 的做法是直接上 01Trie，从而做到单次操作 O(\log_2V) 的时间复杂度。
思考一下为什么这个做法很慢？原因在于 01Trie 每层只有两个分叉，导致层数过深。
那么我们只需要让每层有 w 个分叉即可，这样我们就能做到单次操作 O(\log_wV) 的时间复杂度，这就是压位 Trie 的核心思想。
容易发现，压位 Trie 是一种亚 log 数据结构。
结构
与普通的 01Trie 不同，压位 Trie 的结构是静态的，如下图：
上图是一个四叉的压位 Trie，容易发现其深度就只有 O(\log_wV)，其中 w=4。
其中每个节点维护的是在该位置是否有值，标深色表示有值，每个节点旁边的数字表示其每个儿子是否有值，叶子节点表示每个数。
实际上因为有 `unsgiend long long`，所以大部分的实现都是 $64$ 叉树，从而有 $w=64$，复杂度为 $\log_w V$。
实际实现时似乎把最后一层补满更好?
### 空间复杂度
直接存显然是 $O(V)$ 的。
容易发现我们只需要存每个节点旁边的信息，这样也能表示一棵压位 Trie。那么最后一层就没必要存了，从而得到 $O(\dfrac{V}{w})$ 的空间复杂度。
### 扩展
显然我们在压位 Trie 上可以不止维护每个节点是否有值，还可以维护其它的信息，从而查询更多的问题。
### 具体实现
**压位 Trie 的实现一般都是自底向上的。**
因为这样方便我们剪枝。
- 插入时，如果这个点的父亲已经有这个儿子的信息了，那么它的父亲已经存在了，就不用继续往上算了。
- 删除时，如果这个点的儿子没删完，那么往上都仍然是有信息的，就不用算了。
- 查询前驱后继时，显然让尽量多的位和 $x$ 相同一定更优。
同时，让层数更小的更深，可以简化位运算难度。
具体实现见代码。
### 插入/删除
简单地说就是自底向上更新每个节点的信息，如果信息不变，那么就不需要继续更新了。
### 前驱/后继
显然我们可以通过简单的位运算算出每一层是否有比这个值更大/更小的兄弟，然后钦定前面的每一位都相等，然后再在后面直接取最大/最小即可。
需要使用 `__builtin_clzll` 和 `__builtin_ctzll`。
### 实现
用的是 `vector` 的 `resize`，好像比指针更慢？
```cpp
#include<bits/stdc++.h>
#include"trie.h"
#define ull unsigned long long
using namespace std;
struct _Trie{
const int g=6,mod=63;
vector<ull> a[5];
int dep;
void build(int sz=1<<30){
dep=1;
for(;;++dep){
int cnt=(sz>>g*dep);
a[dep-1].clear(),a[dep-1].shrink_to_fit();
a[dep-1].resize(cnt);
if(cnt==1) return;
}
}
void ins(int x){
for(int i=0;i<dep;++i){
ull p=1ull<<(x>>i*g&mod);
if(a[i][x>>(i+1)*g]&p) return;
a[i][x>>(i+1)*g]|=p;
}
}
void del(int x){ for(int i=0;i<dep;++i) if(a[i][x>>(i+1)*g]&=~(1ull<<(x>>i*g&mod))) return; }
int pre(int x){
for(int i=0;i<dep;++i){
int cur=(x>>i*g&mod);
ull state=a[i][x>>(i+1)*g];
if(state&((1ull<<cur)-1)){
int res=x>>(i+1)*g<<(i+1)*g;
res+=(mod-__builtin_clzll(state&((1ull<<cur)-1)))<<i*g;
for(int j=i-1;~j;--j) res+=(mod-__builtin_clzll(a[j][res>>(j+1)*g]))<<j*g;
return res;
}
}
return 0;
}
int suf(int x){
for(int i=0;i<dep;++i){
int cur=(x>>i*g&mod);
ull state=a[i][x>>(i+1)*g];
if(state>>cur>1){
int res=x>>(i+1)*g<<(i+1)*g;
res+=(__builtin_ctzll(state>>(cur+1))+cur+1)<<i*g;
for(int j=i-1;~j;--j) res+=__builtin_ctzll(a[j][res>>(j+1)*g])<<j*g;
return res;
}
}
return 0;
}
}T;
bool a[200000001];
void init(int n){ T.build(); }
void assign(int i,int x){
if(a[i]==x) return;
if(a[i]) T.del(i);
else T.ins(i);
a[i]=x;
}
int nxt(int i){ return T.suf(i); }
int pre(int i){ return T.pre(i); }
```
### 实操
- [[JSOI2009] 面试的考验 ](https://www.luogu.com.cn/problem/P5926)
- [CF765F Souvenirs](https://www.luogu.com.cn/problem/CF765F)
- [[ZJOI2019] 语言](https://www.luogu.com.cn/problem/P5327)