01Trie

简介

其实就是只有两个分治的 $T r i e$

应用

在 $T r i e$ 里找与 $v$ 的异或的最大值

const int N = 30;
struct Trie {
    int v, ch[2];
} T[maxn * 31]; int rt = 1, top = 1; 
void insert(int k) {
    int i = rt; 
    for (int o = N; ~o; --o) {
        int d = k >> o & 1; 
        if (!T[i].ch[d]) T[i].ch[d] = ++top;
        i = T[i].ch[d];
    } 
}

int query(int i, int k, int o) {
    if (o == -1) return 0;
    int d = k >> o & 1;
    if (T[i].ch[d ^ 1]) return (1 << o) + query(T[i].ch[d ^ 1], k, o - 1);
    else return query(T[i].ch[d], k, o - 1);
}

在 $T r i e$ 里找与 $x$ 异或小于 $y$ 的值的个数

const int N = 30;
#define lc T[i].ch[0]
#define rc T[i].ch[1]
struct Trie {
    int v, ch[2]; 
} T[maxn * 30]; int rt = 1, top = 1;
inline void maintain(int i) { T[i].v = T[lc].v + T[rc].v; } 
void ins(int &i, int k, int o, int v) {
    if (!i) i = ++top; 
    if (o == -1) return (void) (T[i].v += v);
    int d = k >> o & 1; ins(T[i].ch[d], k, o - 1, v);
    maintain(i);
}

int query(int i, int k1, int k2, int o) {
    if (!i) return 0; 
    if (o == -1) return T[i].v;
    int d = k1 >> o & 1, D = k2 >> o & 1;
    if (D) return T[T[i].ch[d]].v + query(T[i].ch[d ^ 1], k1, k2, o - 1);
    else return query(T[i].ch[d], k1, k2, o - 1);
}

在 $T r i e$ 里找异或第 $k$ 小或者前 $k$ 小的和

找第 $k$ 小就用类似权值线段树的方法，下面是一份滚动的代码

for (int o = 61; ~o; --o) {
    top = o & 1 ? 1 : n + 1; 
    for (int i = 1; i <= n; ++i) {
        int &p = a[i], d = w[i] >> o & 1;
        if (!T[p].ch[d]) {
            T[++top].clear();
            T[p].ch[d] = top; 
        }
        ++T[p = T[p].ch[d]].v;
    } ll s = 0; 
    for (int i = 1; i <= n; ++i) {
        int p = b[i], d = w[i] >> o & 1;
        s += T[T[p].ch[d]].v;
    } int v = 0;
    if (k > s) k -= s, ans |= 1ll << o, v = 1;
    for (int i = 1; i <= n; ++i) {
        int &p = b[i], d = w[i] >> o & 1;
        p = T[p].ch[d ^ v]; 
    } 
 }

在 $T r i e$ 里找 $a n d$ 或者 $o r$ 最大值

好像是将 $0$ 的树向 $1$ 的树合并，还没做过

全局加 $1$ ，全局异或和

Luogu P3760 [TJOI2017]异或和(01Trie)

首先我们将 $T r i e$ 按照二进制位从低到高建树

这样我们在加 $1$ 时所进行的操作就是不断进入右子树，然后交换左右子树，然后还要维护异或值

#define lc T[i].ch[0]
#define rc T[i].ch[1]
const int N = 20;
struct Trie {
    int v, sum, ch[2];
} T[Maxn * 21]; int rt = 1, top = 1;
inline void maintain(int i) {
    T[i].v = T[lc].v + T[rc].v;
    T[i].sum = T[lc].sum << 1; 
    T[i].sum ^= T[rc].sum << 1 | T[rc].v & 1; 
} 

void ins(int &i, int k, int o, int v) {
    if (!i) i = ++top;
    if (o == N + 1) return (void) (T[i].v += v);
    int d = k >> o & 1; ins(T[i].ch[d], k, o + 1);
    maintain(i); 
} 

void add(int i) {
    if (!i) return ;
    add(rc); swap(lc, rc);
    maintain(i);
}

例题

简要题意：给定一个长度为 $n$ 的序列 $a_{i}$ ，求所有区间和的异或和

$n \leq 10^{5}, \sum a_{i} \leq 10^{6}$

简要题解：我们要求这个东西 $⨁_{1 \leq j \leq i \leq n} s_{i} - s_{j - 1}$

考虑这样一个做法，我们枚举右端点，维护左端点的异或值

那么每次相当于全局加 $1$ ，求全局异或和，这个东西可以拿 $01 T r i e$ 来做

时间复杂度为 $O ((n + \sum a_{i}) \log \sum a_{i})$

Luogu P3760 [TJOI2017]异或和(01Trie)
简要题解：给定一棵 $n$ 个点有点权的无根树，求第 $k$ 小的路径异或和

$n \leq 10^{6}$

简要题解：找两两异或值的前 $k$ 小类似于在权值线段树上二分

由于爆空间，所以这题只能滚动

CF 1055F Tree and XOR
简要题意：给定一个长度为 $n$ 的序列 $a_{i}$ ，现在要将每个数划分到两个集合，一个几何的权值为集合内的所有数，两两之间的异或和的最小值，现在要求一种分法，使得两个点集的权值的最小值最大

$n \leq 10^{5}$

简要题解：首先考虑一个比较套路的做法，根据 Luogu P1525 [NOIP2010 提高组] 关押罪犯(最小生成树)，容易得到我们只需要求一个最小生成树，然后用 $01 T r i e$ 求一个最小值即可，求异或最小生成树是一个经典的做法，时间复杂度 $O (n \log^{2} n)$

另外还有一个做法，现在我们仿照求异或最小生成树的做法，按位分治

我们考虑现在在考虑第 $k$ 位，令第 $k$ 位为 $1$ 的个数为 $a$ ，第 $k$ 位为 $0$ 的个数为 $b$

注意到如果 $a$ 和 $b$ 都小于等于 $2$ ，那么我们可以通过分组来避免最小值小于 $2^{k}$

否则，最小值一定不含第 $k$ 位，且一定由左边和右边组成，所以可以直接递归

时间复杂度 $O (n \log n)$

The 2020 ICPC Asia Macau Regional Contest C Club Assignment
简要题意：给定一个长度为 $n$ 的数列和一个数字 $k$ ，求从这 $n$ 歌数中找出一个大小最大的子集，满足这个集合中任意两个数的异或和都大于等于 $k$

$n \leq 3 \times 10^{5}$

简要题解：首先得到 $k$ 的最高二进制一的位置，令其为 $t$ ，那么我们容易发现如果如果两个数字 $t$ 之前的位置有所不同，那么这两个数字的异或和一定大于 $k$ ，注意到这是一个前缀的比较，那么我们可以联想到 $01 T r i e$

我们将这些点拉出来，发现他们内部选出来的点与外面的点是没有影响的，然后容易发现，这些点内部最多选两个点，左儿子一个，右儿子一个，因为左右儿子内部选出来的点异或最大不会超过 $2^{t} - 1$ ，那么这里我们只需要枚举左儿子的点，然后对于每个点从右儿子中选一个最大的，在 $01 T r i e$ 上实现这点是非常容易的，最后选择异或和最大的一对点即可

时间复杂度 $O (n \log n)$
CF 1625D Binary Spiders