第七章 树状数组与字典树
树状数组可以很方便的维护序列的前缀和等信息。因此，可以使用树状数组高效完成单点修改、区间求和的任务。虽然线段树也可以完成这些任务，而且时间复杂度都是 $\mathcal{O} (\log n)$，但是树状数组运行时间的常数更小，所需空间更小，代码也更加短小精悍。
字典树可以方便的储存、索引和查找字符串。当然除了字符串，还可以将数字拆成二进制，存入字典树中，常常可以高效处理涉及到异或的问题。
树状数组
例1：P3374 【模板】树状数组 1
例2：P3368 【模板】树状数组 2
例3：P1908 逆序对
字典树
例4：P1481 魔族密码
记 node[u].val 为以 $u$ 节点为末字符的单词个数，则在字典树上访问单词 $str$ 时，所经过的各个 $u$ 节点的 $val$ 之和，即为以 $str$ 为词链末单词时，该词链所包含的单词数。
需要注意的是，题目保证输入顺序按字典顺序排列，故在添加单词 $str$ 时，所有可能对 $res$ 产生贡献的单词都已经被添加过了，因此可以在添加单词时统计 $res$，并将 $ans$ 与之取 $\max$ 即可。
struct TrieTree {
struct Node {
int next[26];
int val;
} node[maxN * maxS + 10];
int tot;
void Insert(std::string str) {
int u = 0;
int res = 1;
for (int i = 0; i < str.size(); i++) {
int ch = str[i] - 'a';
if (node[u].next[ch] == 0) node[u].next[ch] = ++tot;
u = node[u].next[ch];
res += node[u].val;
}
node[u].val++;
ans = std::max(ans, res);
return;
}
} TT;
例5：P2580 于是他错误的点名开始了
字典树基本操作。
需要注意的是，点名时查找字典树都节点，即时已经枚举完名字的所有字符，还是需要判断这个名字是否存在，否则遇到名字时花名册上名字的前缀的情况就出错了。
暑假好像用 $\text{map}$ 艹过去的。
例7：P4551 最长异或路径
SXB1 的作业题。
题目中给出的树没有指定根节点，但可以指定节点 $1$ 为根节点，使其变为有根树。建立这个树，求的第 $i$ 个节点到根节点到异或路径 $s_i$。而节点 $i$ 到节点 $j$ 之间的异或路径就是 $s_i \oplus s_j$。这是因为这两个节点分别到根节点到路径，在他们的最近公共祖先再往上的路径是重叠的，而将相同的边权异或两次就会归零。因此对于所有 $s_i$，找到一个 $s_j$ 使 $s_i \oplus s_j$ 的值最大并记录之，即可求解。
问题在于，如果两两枚举，效率很低，因此可以用 $\text{01-Trie}$ 来维护所有数字的异或和。将每个数字都变成 $31$ 位的二进制数（和值域相关），将其视为一个字符串来建立字典树。所有叶子节点的深度都是一致的。
从二进制数最左边开始，同时字典树从根节点开始，每一位使用贪心策略。如果字典树当前节点只有一个子节点，则直接往下走，否则选择和这一位不同的数对应节点（这样可以使它们的异或值为 $1$）。
struct Trie {
struct Node {
int next[2];
} node[maxN << 5];
int cnt;
void Insert(int val) {
int u = 0;
for (int p = 30; p >= 0; p--) {
bool i = (val >> p) & 1;
if (node[u].next[i] == 0) node[u].next[i] = ++cnt;
u = node[u].next[i];
}
return;
}
int Query(int val) {
int ret = 0;
int u = 0;
for (int p = 30; p >= 0; ip--) {
bool i = (val >> p) & 1;
if (node[u].next[!i]) {
ret += 1 << p;
u = node[u].next[!i];
} else u = node[u].next[i];
}
return ret;
}
} TT;
例7：P5283 [十二省联考 2019] 异或粽子
给定长度为 $n$ 的序列 $a_i$。一个区间 $[l, r] (1 \le r \le n)$ 的价值为从 $a_l$ 到 $a_r$ 之间的每个数字进行的异或值。求这个序列中价值最大的 $k$ 个区间的价值和。
设 $s_i$ 为序列中 $a_1$ 到 $a_i$ 的每个数字依次异或后的结果。则区间 $[l, r]$ 的价值就是 $s_r \oplus s_{l - 1}$。所以对于每一个 $s_i$，都可以找到一个 $s_j$ 使得 $s_i \oplus s_j$ 的值最大。如果能保证 $i \lt j$ 的话，固定 $i$ 为左端点，就可以找到以 $j$ 为右端点的区间 $[i, j]$，使其价值最大了。$s_i$ 和 $s_j$ 互为对偶，所以只需要找 $2k$ 个价值最大的 $(i, j)$ 配对，将其价值累加处以 $2$ 就是答案。
对于每一个 $i$ 找到对应的 $j$，并将其对应的价值放入优先队列中。每次从优先队列中取出价值最大的元素，累加进答案。如果去除的是和 $s_i$ 对应的第 $t$ 大值，则将和 $s_i$ 对应的第 $t + 1$ 大值放入优先队列，重复操作 $2k$ 次即可。
类似于主席树的思想，可以在字典树的插入过程中，记录每个节点的数字数量。在查询的过程中，根据优先往 $0$ 走还是往 $1$ 走，以及左右子节点数量和 $t$ 来决定下一步的方向。
注意 1 << p 是 int 类型，需要写成 1ll << p。
struct TrieTree {
struct Node {
int next[2];
int size;
} node[maxN * (maxP + 1) + 10];
int ncnt;
void Insert(lxl val) {
int u = 0;
for (int p = maxP; p >= 0; p--) {
int i = (val >> p) & 1;
if (node[u].next[i] == 0) {
node[u].next[i] = ++ncnt;
}
u = node[u].next[i];
node[u].size++;
}
return;
}
lxl Query(lxl val, int t) {
lxl ret = 0;
int u = 0;
for (int p = maxP; p >= 0; p--) {
int i = (val >> p) & 1;
if (node[node[u].next[i ^ 1]].size >= t) {
u = node[u].next[i ^ 1];
ret |= 1ll << p;
} else {
t -= node[node[u].next[i ^ 1]].size;
u = node[u].next[i];
}
}
return ret;
}
} TT;
由题意得：
\[1 \le l \le r \le n\]又
\[w(l, r) = s_r \oplus s_{i - 1}\]故对于一个
\[1 \le j \le n\]与之配对的 $i$ 满足
\[0 \le i' \le n - 1, i' = i - 1\]当 $i = 1$ 时，$[i, j]$ 的贡献为
\[\begin{aligned} w(i, j) & = s_j \oplus s_{i - 1} \\ & = s_j \oplus s_0 \\ & = s_j \oplus 0 \\ & = s_j \end{aligned}\]也就是说，在字典树上寻找与 $s_j$ 配对的 $s_i$ 时，$s_0 = 0$ 是需要被考虑在内的。
for (int i = 0; i <= n; i++) TT.Insert(x[i]);
for (int i = 0; i <= n; i++) {
node[i] = (Node) {i, 1, TT.Query(x[i], 1)};
q.push(node[i]);
}
因为在字典树的节点中可以记录所管辖的数字数量，而且对于一个非叶子节点来说，往 “$0$” 方向走可以找到更小的数字，往 “$1$” 方向走可以找到更大的数字，故 $\text{01-Trie}$ 可以完成一些平衡树的操作——插入、删除、根据数据查询排名和根据排名查询数据等。单次操作的复杂度和值域有关。