01-Trie

众所周知，01-Trie 是字符集为 $\begin{Bmatrix}0,1\end{Bmatrix}$ 的 Trie ，可用于维护若干数字的二进制位，处理点对异或最值、某种动态异或和问题。

与线性基不同，01-Trie 无法处理子集异或问题，但是可以通过前缀和转化来处理区间异或问题。

1 简介

01-Trie 支持在 $O(\log a_i)$ 的时间内完成如下操作：

• 查询全局异或和
• 数列全局加一，维护全局异或和
• 查询数列中某个数与指定数字异或的最大值
• 合并两棵 01-Trie 维护的信息

通过将其可持久化，还可以支持如下操作：

• 查询区间异或和
• 查询区间中某个数与指定数字异或的最大值

通过观察容易实现上述若干操作，则可以得到这样一份代码：

/* 非可持久化 */
class TRIE {
  public: int ch[CN * 30][2], d[CN * 30], w[CN * 30], idx, rt, MAXH;
    #define lc ch[u][0]
    #define rc ch[u][1]
    TRIE() {rt = idx = 0, MAXH = 30;}
    int make() {return ++idx;}
    void mt(int u){
        d[u] = 0, w[u] = w[lc] + w[rc];
        if(rc) d[u] ^= (d[rc] << 1) | (w[rc] & 1);
        if(lc) d[u] ^= d[lc] << 1;
        w[u] &= 1;
    }
    void ins(int &u, int x, int dep){                      // 插入一个数
        if(!u) u = make();
        if(dep == MAXH) return (void)(w[u] ^= 1);
        if(x & 1) ins(rc, x >> 1, dep + 1);
        else ins(lc, x >> 1, dep + 1);
        mt(u);
    }
    void add(int u) {if(rc) add(rc); swap(lc, rc), mt(u);} // 全局加一
    int sum() {return d[rt];}                              // 全局异或和
} D;

注意，01-Trie 的可持久化看上去并不支持版本修改，因为无法使用树状数组维护子树交换信息。

2 一道栗题

「TJOI2017」异或和

给定一段数列，定义数列的“连续和”为数列的某个子串的所有数之和，求序列所有连续和的异或值。

考虑固定左端点 $l$ ，$O(n)$ 枚举右端点 $r$ ，则可以求出一些左端点固定的区间 $[l,r]$ 权值和异或和。

考虑优化这个过程：对于一个左端点 $l$ ，如何快速求出其能对应的所有区间 $[l,r]$ 的异或和。由于数列是静态的，那么我们考虑 $l\to l-1$ 时贡献的变化，它应该是这个样子：

$$\begin{aligned} & (s[n]-s[l])\oplus (s[n-1]-s[l])\oplus … \oplus (s[l+1]-s[l]) \newline \to &(s[n]-s[l]+a[l-1])\oplus (s[n-1]-s[l]+a[l-1])\oplus …\oplus a[l-1] \end{aligned}$$

其中 $s[]$ 代表 $a[]$ 的前缀和。容易发现这个变化是对每一项同时加了一个值之后再查询异或和，显然可以通过 01-Tire 来维护，总复杂度 $O((n+\sum a_i)\log a_i)$；由于 $\sum a_i \le 10^6$，所以可以通过。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

const int CN = 1e5 + 5;

int read() { /* 略 */ }
class TRIE { /* 同上 */ } D;

int n, a[CN];
int main()
{
    n = read(); for(int i = 1; i <= n; i++) a[i] = read();

    int ans = 0;
    for(int i = n - 1; i + 1; i--){
        int s = a[i + 1];
        while(s--) D.add( D.rt );
        D.ins(D.rt, a[i + 1], 1);
        ans ^= D.sum();
    }

    printf("%d", ans);
}

3 又一道栗题

「TJOI2018」异或

现在有一颗以 $1$ 为根节点的由 $n$ 个节点组成的树，节点从 $1$ 至 $n$ 编号。树上每个节点上都有一个权值 $v_i$。现在有 $q$ 次操作，操作如下：

• 1 x z：查询节点 $x$ 的子树中的节点权值与 $z$ 异或结果的最大值。
• 2 x y z：查询节点 $x$ 到节点 $y$ 的简单路径上的节点的权值与 $z$ 异或结果最大值。

容易想到树剖，则转化为序列上的查询操作。通过版本来区分区间，即将 01-Tire 可持久化，即可解决本题。

可持久化 01-Trie 一般用于处理静态区间异或最大值问题。

容易得到如下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 5e5 + 5;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}

class TRIE {
  public: int rt[CN], ch[CN * 30][2], w[CN * 30], MAXH, idx;
    #define lc ch[u][0]
    #define rc ch[u][1]
    TRIE() {idx = 0, MAXH = 31;}
    int make() {return ++idx;}
    void ins(int &u, int v, int x, int dep){
        if(!u) u = make(); if(dep < 0) return (void)(w[u] = w[v] + 1);
        int b = (x >> dep) & 1; ch[u][!b] = ch[v][!b];
        ins(ch[u][b], ch[v][b], x, dep - 1);
        w[u] = w[lc] + w[rc];
    }
    int qm(int u, int v, int k, int dep){
        if(dep < 0) return 0;
        int b = (k >> dep) & 1;
        if(w[ ch[u][!b] ] > w[ ch[v][!b] ]) return (1 << dep) | qm(ch[u][!b], ch[v][!b], k, dep - 1);
        else return qm(ch[u][b], ch[v][b], k, dep - 1);
    }
} D;

int n, q, v[CN], oid[CN];

int top[CN], id[CN], sz[CN], imp[CN], dep[CN], fa[CN], idx = 0;
void dfs1(int u, int p) {
    dep[u] = dep[p] + 1, sz[u] = 1, fa[u] = p; int mx = 0;
    for(int k = hd[u]; k; k = E[k].nxt){
        int v = E[k].to;
        if(v ^ p) dfs1(v, u), sz[u] += sz[v], mx = sz[v] > mx ? imp[u] = v, sz[v] : mx;
    }
}
void dfs2(int u, int t){
    top[u] = t, id[u] = ++idx;
    if(imp[u]) dfs2(imp[u], t);
    for(int k = hd[u]; k; k = E[k].nxt){
        int v = E[k].to;
        if(v ^ imp[u] && v ^ fa[u]) dfs2(v, v); 
    }
}
int qu(int x, int y, int z){
    int ans = 0;
    while(top[x] != top[y]){
        if(dep[ top[x] ] < dep[ top[y] ]) swap(x, y);
        ans = max(ans, D.qm(D.rt[ id[x] ], D.rt[ id[ top[x] ] - 1 ], z, D.MAXH));
        x = fa[ top[x] ];
    }
    if(dep[x] < dep[y]) swap(x, y);
    ans = max(ans ,D.qm(D.rt[ id[x] ], D.rt[ id[y] - 1 ], z, D.MAXH));
    return ans;
}

bool cmp(int x, int y) {return id[x] < id[y];}

int main()
{
    n = read(), q = read();
    for(int i = 1; i <= n; i++) v[i] = read(), oid[i] = i;
    for(int i = 1; i < n; i++) {int u = read(), v = read(); add(u, v), add(v, u);}

    dfs1(1, 0), dfs2(1, 1);
    sort(oid + 1, oid + n + 1, cmp);
    for(int i = 1; i <= n; i++) D.ins(D.rt[i], D.rt[i - 1], v[ oid[i] ], D.MAXH);

    while(q--){
        int o = read(), x = read(), y = read(), z;
        if(o == 1) printf("%d", D.qm(D.rt[ id[x] + sz[x] - 1 ], D.rt[ id[x] - 1 ], y, D.MAXH)), puts("");
        else z = read(), printf("%d", qu(x, y, z)), puts("");
    }
}

4 双一道栗题

「联合省选 2020 A」树

给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。
设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_1,c_2,\dots,c_k$，定义 $x$ 的价值为：
$$val(x)=(v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k, x))$$
其中 $d(x,y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数，$d(x,x) = 0$。$\oplus$ 表示异或运算。
请你求出 $\sum\limits_{i=1}^n val(i)$ 的结果。

对每个叶子建立一棵 01-Trie ，然后每次合起来再全局加一即可得到父亲的 01-Trie ，统计答案即可。

01-Trie 合并的序列意义是：把两段序列的所有数字插入同一个 01-Trie ，并维护异或和。

容易得到如下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

const int CN = 6e5+5;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;}}E[CN << 2];
int hd[CN],ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}

class trie{ // dep = 0,dep > 20
  public: int ch[CN * 30][2], w[CN * 30], val[CN * 30], rt[CN], tot;
    trie() {memset(rt, 0, sizeof(rt)); tot = 0;}
    #define lc ch[u][0]
    #define rc ch[u][1]
    int make() {int u = ++tot; lc = rc = w[u] = val[u] = 0; return tot;}
    void maintain(int u){
        w[u] = val[u] = 0;
        if(lc) w[u] += w[lc], val[u] ^= val[lc] << 1;
        if(rc) w[u] += w[rc], val[u] ^= (val[rc] << 1) | w[rc];
        w[u] &= 1;
    }
    void ins(int &u,int x,int dep){
        if(!u) u = make();
        if(dep > 20) return (void)(w[u] ^= 1);
        ins(ch[u][x & 1], x >> 1, dep + 1);
        maintain(u);
    }
    void addall(int u) {if(rc) addall(rc); swap(lc, rc); maintain(u);}
    int merge(int u,int k){
        if(!k) return u; if(!u) return k;
        w[u] = (w[u] + w[k]) & 1; val[u] ^= val[k];
        lc = merge(lc, ch[k][0]); rc = merge(rc, ch[k][1]);
        return u;
    }
}D;

int n,v[CN],va[CN];

void dfs(int u){
    if(!hd[u]){
        va[u] = v[u];
        D.ins(D.rt[u], v[u], 0);
        return;
    }

    int k = hd[u], s1;
    for(; k; k = E[k].nxt) dfs(E[k].to);
    
    k = hd[u], s1 = E[k].to, k = E[k].nxt, D.rt[u] = D.rt[s1];
    for(; k; k = E[k].nxt){
        int v = E[k].to;
        D.merge(D.rt[u], D.rt[v]);
    }
    D.addall(D.rt[u]), D.ins(D.rt[u], v[u], 0);
    va[u] = D.val[ D.rt[u] ];
}

int main()
{
    n = read();
    for(int i = 1;i <= n;i++) v[i] = read();
    for(int i = 2;i <= n;i++) add(read(), i);

    dfs(1);

    long long ans = 0;
    for(int i = 1;i <= n;i++) ans += 1ll * va[i];

    printf("%lld", ans); 
}