01 字典树
前置知识：字典树。
01 字典树是一种特殊的字典树，它会把数字看作二进制的 \(\texttt{01}\) 串存入字符串。
在树上，除了叶子节点外的所有节点都表示一个数的范围。
我们在插入元素时，和在字典树中插入元素时类似的。这里不再阐述。
插入示例代码如下：
const int MAXN = 2e6 + 5, MAXL = 31;
int tr[MAXN][2], cnt[MAXN], r = 1;
void insert(int x){
int u = 1;
for (int j = 30; j >= 0; j--){
int v = (x >> j) & 1;
if (!tr[u][j]){
tr[u][j] = ++r;
}
u = tr[u][j];
cnt[u]++;
}
}
如果我们把每个节点表示的数字都存储下来，那么就会是这样：
再修改一下，就变成了这样：
\[[0,7]\to\begin{cases} [4,7]\to\begin{cases} [6,7]\to\begin{cases} [6]\\ [7]\\ \end{cases} \\ [4,5]\to\begin{cases} [4]\\ [5] \end{cases}\\ \end{cases}\\ [0,3]\to\begin{cases} [2,3]\to \begin{cases} [2]\\ [3] \end{cases} \\ [0,1]\to\begin{cases} [0]\\ [1] \end{cases} \end{cases} \end{cases} \]那么我们就可以发现：每个节点表示的数字都是一个区间。\(\color{white}{是不是很像线段树？}\)
那么 01 字典树能做些什么呢？它通常用来解决一些与位运算有关的问题。具体我们来看题。
当然，我们也可以使用 01 字典树以 \(O(\log_2 x)\) 的时间复杂度判断一个数字 \(x\) 是否出现过。相比于
map，常数会小很多。
例 1：洛谷 U77096 字典树|the xor largest pair
题意：给定 \(n\) 个正整数 \(A_1,A_2,\dots,A_n\)，求出 \(\max\limits_{x\in A,y\in A}\{x\oplus y\}\)
数据范围：\(1\le n\le 10^5,0\le A_i\le 2^{31}\)。
本题我们就可以使用 01 字典树完成。
首先，对于异或来说，\(1\oplus 0=0\oplus 1=1\)。
那么，如果我们想让这个异或值最大，对于 \(a_i\)，我们选择的匹配的数字的每一位就要尽可能的与 \(a_i\) 的对应位不同。
那么，我们在存储时记录下对应位置 \(x\) 中 0、1 的是否出现过，查找时尽量匹配与 \(a_i\) 对应位不同的数，最后对答案求最大值即可。
参考代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 7e6 + 5, MAXL = 31;
int tr[MAXN][2], r = 1, n, a[MAXN];
bool cnt[MAXN];
void insert(int x){
int u = 1;
for (int j = 30; j >= 0; j--){
int v = (x >> j) & 1;
if (!tr[u][v]){
tr[u][v] = ++r;
}
u = tr[u][v];
cnt[u] = 1;
}
}
int find(int x){
int u = 1, ans = 0;
for (int j = 30; j >= 0; j--){
int v = (x >> j) & 1;
if (tr[u][(v ^ 1)] && cnt[tr[u][v ^ 1]]){
u = tr[u][(v ^ 1)];
ans |= ((v ^ 1) << j);
}else if (tr[u][v] && cnt[tr[u][v]]){
u = tr[u][v];
ans |= (v << j);
}else {
return ans;
}
}
return ans;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
insert(a[i]);
}
long long ans = -1;
for (int i = 1; i <= n; i++){
ans = max(ans, 1ll * (a[i] ^ find(a[i])));
}
cout << ans;
return 0;
}
但是，如果这道题还增加了一个操作呢？那么就来到了下一题。
例二：CodeForces-706-D Vasiliy's Multiset
题意：有 \(q\) 次询问。初始序列 \(A\) 中只有一个数字 \(0\)。每次询问属于以下三种操作之一：
1.+ x 表示将 \(x\) 加入序列 \(A\)。
2.- x 表示将 \(x\) 从序列 \(A\) 中删除。如果序列中有多个 \(x\)，那么只删除一个。
3.? x 表示求出 \(\max\limits_{y\in A}\{x\oplus y\}\)。
对于每次询问 \(3\)，输出一个数表示答案。
数据范围：\(1\le q\le 2\times 10^5,0\le A_i\le 10^9\)。
本题的其他实现与例 1 类似。但是增加了一个删除操作。
我们可以对 cnt 数组进行修改。从记录一个位置是否出现过改为一个位置出现过的次数。
删除操作就只要对对应位置的的出现次数减一即可。
参考代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 7e6 + 5, MAXL = 31;
int tr[MAXN][2], cnt[MAXN], r = 1;
void insert(int x){
int u = 1;
for (int j = 30; j >= 0; j--){
int v = (x >> j) & 1;
if (!tr[u][v]){
tr[u][v] = ++r;
}
u = tr[u][v];
cnt[u]++;
}
}
int find(int x){
int u = 1, ans = 0;
for (int j = 30; j >= 0; j--){
int v = (x >> j) & 1;
if (tr[u][(v ^ 1)] && cnt[tr[u][v ^ 1]]){
u = tr[u][(v ^ 1)];
ans |= ((v ^ 1) << j);
}else if (tr[u][v] && cnt[tr[u][v]]){
u = tr[u][v];
ans |= (v << j);
}else {
return ans;
}
}
return ans;
}
void del(int x){
int u = 1;
for (int j = 30; j >= 0; j--){
int v = (x >> j) & 1;
u = tr[u][v];
cnt[u]--;
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int q;
cin >> q;
insert(0);
while (q--){
char s;
int x;
cin >> s >> x;
if (s == '+'){
insert(x);
}else if (s == '-'){
del(x);
}else {
cout << (x ^ find(x)) << '\n';
}
}
return 0;
}
例 3：HDU-6955 Xor sum
题意：有 \(t\) 组数据，每组数据给定一个长度为 \(n\) 的序列 \(a\)。请你找出一个异或和不小于 \(k\) 的最短连续子串。
如果有多个满足要求的连续子串，输出左端点最小的。
如果不存在这样的序列，输出 -1。
数据范围：\(1\le t\le 100,1\le n\le 10^5,0\le k\le 2^{30},0\le a_i\le 2^{30}\)。
我们注意到，如果存在一个序列 \(a_1,a_2,a_3,a_4\)，那么有 \(a_3\oplus a_4=a_1\oplus a_2\oplus a_3\oplus a_4\oplus a_1\oplus a_2\)。
也就是说，异或满足类似前缀和的思路。
所以，我们可以对序列 \(a\) 求前缀异或和，存储在数组 \(b\) 中。
此时，问题就转化为了：求两个数 \(l,r\)，要求 \(l\) 和 \(r - l + 1\) 都最小，并且满足 \(b_r\oplus b_{l-1}\ge k\)。
现在，来考虑 insert 和 find 函数的实现。
我们可以把 \(cnt\) 数组记录的东西修改一下。因为我们要在满足条件的条件下使得在 \(r\) 一定的情况下 \(l\) 最大，那么我们就可以记录对应位置的 \(l\) 的最大值。
insert 函数的实现如下：
void insert(int x, int l){
int u = 1;
for (int j = 30; j >= 0; j--){
int v = (x >> j) & 1;
if (!tr[u][v]){
tr[u][v] = ++r;
}
u = tr[u][v];
cnt[u] = max(cnt[u], l);
}
}
接下来是 find 函数。
首先我们需要让区间异或和 \(x\ge k\)，那么我们就看 \(k\) 的其中一个位数是 \(0\) 还是 \(1\)。如果这一位是 \(1\)，那么我们在选择数字的时候就只能选择 \(0\)。否则，\(0\)、\(1\) 都可以选择。
如果这一位是 \(0\)，那么对应位是 \(1\) 的一定满足答案的要求。此时就可以更新答案。
最后整合输出即可。
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXV = 7e6 + 5, MAXL = 31, MAXN = 1e5 + 5;
int n, k, r = 1, t, tr[MAXV][2], a[MAXN], qz[MAXN], cnt[MAXV];
void insert(int x, int l){
int u = 1;
for (int j = 30; j >= 0; j--){
int v = (x >> j) & 1;
if (!tr[u][v]){
tr[u][v] = ++r;
}
u = tr[u][v];
cnt[u] = max(cnt[u], l);
}
}
int find(int x){
int u = 1, ans = 0;
for (int j = 30; j >= 0; j--){
int v = (x >> j) & 1, z = (k >> j) & 1;
if (z){
u = tr[u][(v ^ 1)];
}else {
ans = max(ans, cnt[tr[u][(v ^ 1)]]);
u = tr[u][v];
}
}
return max(ans, cnt[u]);
}
void Solve(){
for (int i = 1; i <= r; i++){
tr[i][0] = tr[i][1] = cnt[i] = 0;
}
r = 1;
cin >> n >> k;
int ansl = -1, ansr = 1e9;
for (int i = 1; i <= n; i++){
cin >> a[i];
qz[i] = (qz[i - 1] ^ a[i]);
insert(qz[i - 1], i);
int x = find(qz[i]);
if (x > 0 && i - x < ansr - ansl){
ansl = x, ansr = i;
}
}
if (ansl == -1){
cout << "-1\n";
}else {
cout << ansl << ' ' << ansr << '\n';
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> t;
while (t--){
Solve();
}
return 0;
}
例 4：洛谷-P3369 普通平衡树
题意：有 \(n\) 次询问，每次询问格式为 op x。具体含义如下：
- \(op=1\)：插入数字 \(x\)。
- \(op=2\)：删除数字 \(x\)。如果有多个，就只删除一个。
- \(op=3\)：询问 \(x\) 的排名。一个数的排名为比它小的数字加一。
- \(op=4\)：查询排名为 \(x\) 的数字。
- \(op=5\)：求小于 \(x\) 且最大的数。
- \(op=6\)：求大于 \(x\) 且最小的数。
数据范围：\(1\le n\le 10^5,|x|\le 10^7,1\le op\le 6\)。
虽然这题叫做平衡树，但是我们也可以使用 01 字典树实现。
首先观察到 \(x\) 可以为负数，但 01 字典树不能使用负数，所以我们就整体加上偏移量 \(10^7\)，输出的时候再减去 \(10^7\) 即可。
操作一二没啥好说的，和上面的一样。
对于操作三，我们发现：如果当前位是 \(1\)，那么当前位是 \(0\) 的一定都小于当前数。答案累加即可。
代码如下：
void finda(int x){
int ans = 0, u = 1;
for (int j = 25; j >= 0; j--){
int v = (x >> j) & 1;
if (v){
ans += cnt[tr[u][0]];
}
u = tr[u][v];
}
cout << ans + 1 << '\n';
}
操作四和操作三差不多。代码如下：
void findb(int x){
int u = 1, ans = 0;
for (int j = 25; j >= 0; j--){
if (cnt[tr[u][0]] < x){
x -= cnt[tr[u][0]];
u = tr[u][1];
ans |= (1ll << j);
}else {
u = tr[u][0];
}
}
int p = 1e7;
cout << ans - p << '\n';
}
但是对于操作五和操作六呢？
我们可以发现：比 \(x\) 小且最大的数字的排名一定是 \(x\) 的排名减一。那么答案就是 findb(finda(x)-1)。
那么操作六也差不多。比 \(x\) 大且最小的数字的排名也就是 \(x\) 的排名加上 \(x\) 的出现次数 \(p\)。那么答案就是 findb(finda(x)+p)。
当然操作五六也可以使用 multiset 进行维护。这里我们不在探讨。
最后，还是希望大家能把上面的四道例题消化好，在 OI 的道路上砥砺前行！
标签：cnt,le,int,tr,笔记,--,01,cases,字典 From： https://www.cnblogs.com/tianbiandeshenghuo/p/01-trie-stuty-note.html