P6018 [Ynoi2010] Fusion tree

题目背景和题意无关，可以跳过。 ## 1. 前言： Fusion Tree，中文译作融合树，是一种亚 $\log$ 的数据结构，于 1993 年由 Michael L. Fredman 和 Dan E. Willard 提出。 用途：$O(\frac{\log n}{\log w} + \log w)$ 时间复杂度支持插入，删除，前驱，后继，$\operatorname{min}$，$\operatorname{max}$，以及用于整数排序。 信息论断言对 $n$ 个数的排序在最坏情况下需要 $n \log n$ 次比较，不过对这个界我们还需要一些研究。 有人证明了任意 unit cost RAM 算法，其中只包含加法，减法，乘法，和 $0$ 比较（但是不包含除法和位运算）最坏情况下需要 $\Omega(n \log n)$ 的时间去对 $n$ 个数排序。 如果允许使用除法和位运算，他们有一个线性时间复杂度的算法，但是这个算法对 unit cost 滥用。 这里我们规定我们使用的计算模型的字长是 $w$，每个输入的数都是在 $[0, 2 ^ w - 1]$ 中的整数。 ## 2. 一些记号： 对于一个集合 $S$ 和一个整数 $x$，定义 $rank(S, x)$ 为 S 集合中 $\le x$ 的元素个数。 对于一些非负整数 $a$，定义 $bin(a_1, ..., a_n) = 2 ^ {a_i} + ... + 2 ^ {a_n}$。 对于两个非负整数 $a, b$，定义 $msb(u, v)$ 为 $u$ 和 $v$ 最高的不相同的位。 ## 3. 概述： Fusion Tree 大概可以看做是一棵特殊的 B-Tree，特性： 1. 叉数 $B = O(w ^ {1 / 5})$ 2. 在一次搜索时，每个在搜索路径上的节点的正确的儿子可以被 $O(1)$ 确定 从这些特性我们可以看出 Fusion Tree 单次操作的时间复杂度是 $O(\log_w(n) + \log w) = O(\frac{\log n}{\log w} + \log w)$ 的，比 $O(\log n)$ 低。 但是由于其实现方式，Fusion Tree 每次对内部节点的更新复杂度是 $O(B ^ 4)$ 的。 为了控制 Fusion Tree 均摊的更新复杂度，我们将这棵 B-Tree 的每对叶子节点之间的部分替换为一个大小大约为 $O(B ^ 4)$ 的 Weight Balanced Tree，只在 WBT 根节点发生变化的时候更新 Fusion Tree 的内部节点。 具体来说，我们 B-Tree 维护的是一个排序后的数组的分块，其中每个块都由一棵平衡二叉搜索树维护，fusion tree 上只维护一个值来表示块边界，用途是指引每次插入，删除，查询在哪个块中。 可以发现这样我们把内部节点的变化次数除掉了一个 $B ^ 4$。 ## 4. 压缩 key 的表示： 如何 $O(1)$ 确定搜索路径上的一个节点的正确的儿子： 考虑一个 B-Tree 的节点，其上面包含了 $k$ 个 key，其中 $\frac{B}{2} \le k \le B$，记作 $S = \{u_1, u_2, ..., u_k\}$。 然后我们定义出 $B(S)$ 表示 "有区别的位的位置"，用人话来说就是我们把这 $k$ 个 key 的 trie 建出来，然后所有有超过 $1$ 个儿子的节点的高度构成的集合 （当然这里我们不用把 trie 建出来，只是这么解释比较直观，而且更能反映出其的一些性质）。 再定义一个集合 $K(S)$，为 $S$ 只保留 $B(S)$ 中那些位之后的值，记作 $K(S) = \{u'_1, u'_2, ..., u'_k\}$，发现这个压缩操作对于原集合是保序的。 对于一个任意的 w-bits 的数 $u$，我们记 $u'(S)$ 表示 $u$ 只保留 $B(S)$ 中那些位，即把非 $B(S)$ 中的位都置为 $0$ 之后的值。 下面引理表达了一个压缩 key 的重要性质： ### 引理 1： 设 $B(S)$ 排序后为 $c_1 < c_2 < ... < c_r$，定义边界 $c_0 = -1, c_{r + 1} = b$。 定义 $u'_i$ 为 $K(S)$ 中任意的一个压缩后的 key。 对于一个任意的 w-bit 的数 $u$，满足 $u \neq u_i$， 设 $msb(u'(S), u'_i) = c_m$，即 $u$ 和 $u_i$ 在 bit 位置 $c_{m + 1}, ... , c_r$ 位置处相等，但是在 $c_m$ 处不相等，如果 $u'(S) = u'_i$，则我们记 $m = 0$。 如果 $u$ 和 $u_i$ 不同的最高位 $p$ 满足 $p > c_m$，那么我们可以通过： 1. 唯一的一个区间 $[c_{j - 1}, c_j]$ 满足 $p$ 属于这个区间 2. $u$ 和 $u_i$ 的大小关系 来确定 $rank(S, u)$ 的值。 证明平凡，把 trie 画出来，显然可以画成一个平面图，然后可以发现这两个可以唯一地确定出一个平面区域，这个区域中的 $S$ 集合元素个数就是 $rank(S, u)$（感觉这种东西光写一堆自然语言也不能说明正确性，需要形式化证明一下？）。 注意到这个引理虽然是对任意 $u_i$ 成立的，但是要求 $u$ 和 $u_i$ 不相同的最高位不是 $B(S)$ 中的一个点，可以发现这个 $u_i$ 其实必须在 $u$ "脱离" 这个 trie 的位置，也就是 $p$ 的父亲子树中。 引理 $1$ 使得我们可以将 $rank(S, u)$ 的计算规模降低到 $rank(K(S), u'(S))$，通过计算 $rank(K(S), u'(S))$，我们可以确定 $u'(S)$ 在 $K(S)$ 中的前驱后继 $u'_j$ 和 $u'_{j + 1}$（这两个值不一定存在，但经过平凡的讨论就可以解决。 如果 $u_j \le u \le u_{j + 1}$，那我们已经解决了这个问题 否则我们令 $i = j$ 或者 $i = j + 1$，计算出 $msb(u_i, u) = p$，然后只要我们知道了包含 $p$ 的区间 $[c_j, c_{j + 1}]$，我们就可以通过引理 $1$ 来确定出 $rank(S, u)$ 的值。 这里如果我们 $u_j \le u \le u_{j + 1}$，那我们已经达成了目的，不用继续考虑了。 否则如果不满足 $u_j \le u \le u_{j + 1}$，也就是说我们在这个 sketch 的过程中丢失了信息，即说明保留 $K(S)$ 这些位的信息是不够的，那么 $p$ 一定不在 $K(S)$ 中，也就是说 $i = j$ 和 $i = j + 1$ 中 $p$ 较小的 $i$ 满足 $p > c_m$，故可以使用引理 $1$。 计算 $K(S)$ 和 $u'(S)$： 我们发现没有平凡的方法可以将一个 w-bit 的数 $u$ 在 $O(1)$ 时间把 $B(S)$ 那些位提取出来之后放到连续的一段中（可能可以通过硬件支持实现？），即使经过了一定预处理。 其实我们不需要做到这个，可以用具有： 1. 将需要提取出的位提取出，并放到（可以不连续）的更短的一段中 2. 保序性 的其他变化来实现我们需要的效果。 我们可以通过一次恰当的乘法和一次与运算来实现这个： 沿用引理 $1$ 的定义，设我们需要从 $u$ 中提取这些位，令 $C = bin(c_1, ... , c_r)$。 假设我们已经算出了 $C$，我们先通过令 $v = u \operatorname{and} C$ 来将 $u$ 中不需要的那些位置 $0$。 然后我们将 $v$ 乘以一个量 $M$，从而把 $v$ 中我们需要的那些 $bit$ 转化到一个狭窄的范围内，然后再通过一次 $\operatorname{and}$ 来清除掉不需要的位置 这里给出对一个量 $M$ 的存在性证明和构造： 记 $M = bin(m_1, ..., m_r)$，如果我们暂时忽略交叉和进位造成的影响，那么可以认为 $v$ 乘 $M$ 是把 $c_1, ..., c_r$ 这些位置的位重新定位到了。 $c_1 + m_1, ... , c_r + m_r$ 上。 如果对任意 $1 \le i, j \le r$，这 $r ^ 2$ 个 $c_i + m_j$ 都是不同的，那么就不会发生交叉和进位了。 我们现在的目标是构造一个整数集合 $\{m_1, ... , m_r\}$，使得： 1. $c_1 + m_1 < c_2 + m_2 < ... < c_r + m_r$ 2. 对任意 $1 \le i, j \le r$，$c_i + m_j$ 都是两两不同的。 3. 变换后的区间 $[c_1 + m_1, c_r + m_r]$ "相对较小"，这里的相对较小其实只要是 $O( \operatorname{poly}(r))$ 的即可，因为这样我们可以通过调整树的叉数来满足后续的条件。 ### 引理 2： 给一个 $r$ 个整数的序列，$c_1 < ... < c_r$，存在一个 $r$ 个整数的序列，$m_1, ..., m_r$，满足： 1. $c_1 + m_1 < c_2 + m_2 < ... < c_r + m_r$ 2. 对任意 $1 \le i, j \le r$，$c_i + m_j$ 都是两两不同的。 3. $(c_r + m_r) - (c_1 + m_1) \le r ^ 4$ 证明： 先考虑证明存在整数序列 $m'_1, ... , m'_r$，使得对任意 $i, j, a, b$，$m'_i + c_a$ 与 $m'_j + c_b$ 在模 $r ^ 3$ 的意义下不同余。 如果我们找到了这样的整数序列，那么所有 $r ^ 2$ 个 $c_i + m'_j$ 都是两两不同的，并且由于这个是在模 $r ^ 3$ 意义下两两不同的，所以我们可以对第 $i$ 个 $c_i + m'_i$ 加上 $(i - 1) \cdot r ^ 3$，这样就可以保证对所有 $i$ 满足 $c_i + m'_i < c_{i + 1} + m'_{i + 1}$ 了。 关于 $m'_1, ... , m'_r$ 的存在性： 使用数学归纳法来证明，显然我们可以找到 $m'_1$，这个平凡。 假设结论对 $t$ 成立，即我们已经找到了 $m'_1, ..., m'_t$，满足对任意 $1 \le i, j \le t$，$a, b$, 有 $m'_i + c_a$ 与 $m'_j + c_b$ 在模 $r ^ 3$ 的意义下不同余。 可以观察到 $m'_{t + 1} + c_i \equiv m'_s + c_j \pmod {r ^ 3}$，即 $m'_{t + 1} \equiv m'_s + c_j - c_i \pmod {r ^ 3}$。 我们可以令 $m'_{t + 1}$ 是 $[0, r ^ 3)$ 中最小的和所有 $m'_s + c_j - c_i$ 不同余的数，这里 $1 \le s \le t, 1 \le i, j \le r$。 由鸽巢原理，由于 $t * r ^ 2 < r ^ 3$，所以我们一定可以找到 $m'_{t + 1}$。 故当 $t + 1 \le s$ 时，结论对 $t + 1$ 成立 由数学归纳法知结论对 $s$ 成立，同时我们这里给出了一个暴力的 $O(r ^ 4)$ 的构造算法（$r$ 轮，每轮最坏枚举 $O(r ^ 3)$ 个位置）。 ## 5. 融合： 融合树的 "融合" 即指将每个节点上的 key 放到同一个 w-bit 的 word 上，通过对这个 word 进行运算来一起处理这些 key。 沿用之前 $u_i$ 和 $B(S) = \{c_i\}$ 的记号： 我们这个 B-Tree 的每个节点存了 $C = bin(c_1, ..., c_r)$ 和 $M = bin(m_1, ..., m_r)$ 这两个量，用于计算 $u'(S)$，同时还存了 $D = bin(c_1 + m_1, ..., c_r + m_r)$ 这个量，用于清空 $u'(S)$ 的计算中不需要的位。 同时还需要两个数组，存排序后的 $u_i$ 和 $u'_i$，和一个表 $f_{i, j, 2}$ 表示引理 $1$ 中，如果知道了 $u_i$ 和 $j$，还有 $u$ 和 $u_i$ 的大小关系，我们唯一确定的答案是多少。 回顾之前的内容，当我们算出了 $j = rank(K(S), u'(S))$ 后，如果 $u$ 不在 $[u_j, u_{j + 1}]$ 的区间中，那么我们把 $u'(S) \operatorname{xor} u'_j$ 和 $u'(S) \operatorname{xor} u'_{j + 1}$ 比较一下，较小的值所对应的 $u'_h$，$h = j$ 或 $j + 1$，和 $u$ 有更长的公共前缀，即 $msb$ 更小。 令 $m = msb(u, u_h)$，然后我们需要知道 $m$ 被哪个 $B(S)$ 中的区间 $[c_i, c_{i + 1}]$ 包含，所以需要进行一次 $i = rank(B(S), m)$ 的计算 还需要进行一次 $u$ 和 $u_h$ 的比较，这个平凡，当这些都做完了，我们查一下表 $f$ 即可得到 $rank(S, u)$。 可以发现 fusion tree 的每个内部节点需要存下 $O(B ^ 2 $ 大小的表，内部节点个数是 $O(n / B ^ 4)$ 个，所以是 $O(n)$ 空间的。 下面给出对 1. $rank(K(S), u'(S))$ 2. $rank(B(S), m)$，其中 $m$ 是在 $[0, w]$ 中的整数 3. 两个 $w-bit$ 的整数 $u, v$，$msb(u, v)$ 的计算方法： ### $O(1)$ 计算 $rank(K(S), u'(S))$： 我们把每个 $K(S)$ 中的元素前面补一个 $1$，然后从小到大拼到一起来，这个拼起来的操作就是所谓的 "融合"。 由于我们 $K(S)$ 中有 $k$ 个元素，每个元素有 $r ^ 4$ 位，所以这里总共用了 $k \cdot (r ^ 4 + 1)$ 位，由于 $\frac{B}{2} \le k \le B$，所以我们总的位数是 $O(B ^ 5)$ 的，由于 $B = O(w ^ \frac{1}{5})$，所以总的位数是 $O(w)$ 的。 所以我们拼起来的这个东西是 $O(1)$ 个 word 的，这里将其定义为 $A$。 令 $C = \sum \limits_{i = 0} ^ {B} 2 ^ {(r ^ 4 + 1) \cdot i}$ 通过 $u'(S) \times C$，可以将 $u'(S)$ 前面补一个 $0$ 之后复制 $B$ 遍，然后拼到一起 通过 $A - u'(S) \times C$，可以发现对每个 $A$ 中补 $1$ 的位置，其对应的那个 $u_i(S)$ 如果 $< u'(S)$，则这个 $1$ 变成 $0$，否则 $1$ 不变 所以我们通过 $(A - u'(S) \times C) \operatorname{and} C$，然后对这个 word 数 $1$ 的个数即可知道 $rank(K(S), u'(S))$。 由于这个 word 只在 $2 ^ {(r ^ 4 + 1) \cdot i}$ 这样的位置有 $1$，我们可以通过一次对 $2 ^ {r ^ 4 + 1} - 1$ 的取模来得到其中 $1$ 的个数，虽然对常数取模可以用乘法和位运算 $O(1)$ 实现，但我们这里可以给出一个更合适的构造。 我们可以通过将其乘 $C \operatorname{and} \ (2 ^ {(r ^ 4 + 1) \cdot k} - 1)$，这样相当于把其叠加了 $k$ 次之后加起来，可以发现其中有一个长为 $r ^ 4 + 1$ 的段，这段的二进制表示的值等于这个 word 在 $2 ^ {(r ^ 4 + 1) \cdot i}$ 这些位置的元素的和。 通过位移和 $\operatorname{and}$ 我们可以取出这个长 $r ^ 4 + 1$ 的段，于是就完成了。 答案即 $((((A - u'(S) \times C) \operatorname{and} C) \times (C \operatorname{and} \ (2 ^ {(r ^ 4 + 1) \cdot k} - 1))) \operatorname{and} C) >> ((k (r ^ 4 + 1) - 1)$ ### $O(1)$ 计算 $rank(B(S), m)$，$m$ 是在 $[0, w]$ 中的整数： 由于我们可以 $O(1)$ 计算 $rank(K(S), u'(S))$，所以把这个查出来然后判断那一个数的大小，并且进行一次查表即可。 ### $O(1)$ 计算 $msb(u, v)$： 等价于求 $u \operatorname{xor} v$ 的最高位 $1$ 的位置，设 $A = u \operatorname{xor} v$。 我们将 $A$ 分为 $r ^ c$ 大小的块，总共 $r$ 块，这里 $c$ 是一个常数, $c > 1$ 令 $C = (100...0100...0......)_2$，这里每两个 $1$ 之间有 $r - 1$ 个 $1$，$C$ 是一个常数。 注意到： $((100...0)_2 - 0) \operatorname{and} \ (1 (w - r)$ 可以将每块首位的数字拼到一个长 $r$ 的二进制数中。 然后我们可以使用前面的 $O(1)$ 计算 $rank$ 的方法，令 $B'(S) = \{2 ^ i\}$，$i$ 在 $[0, r - 1]$ 间，是整数。 通过 $rank(B'(S), (((A \operatorname{and} C) \operatorname{or} \ (C - ((C - (A \operatorname{and} \ (\sim C))) \operatorname{and} C)) \times D)) >> (w - r)$ 就可以得到这个长 $r$ 的二进制数中第一个非 $0$ 的首位的位置了。 我们知道了第一个非 $0$ 位在哪个块中，然后查这个块里面第一个非 $0$ 位的位置就可以了。 由于我们每个块是 $r ^ c$ 的大小，所以对一个大小为 $r ^ c$，包含了 $2 ^ i$ 的集合用一次 rank 即找到了块内第一个非 $0$ 的首位位置。 取 $c = 4, r = w ^ {1 / 5}$，$r ^ c = w ^ {4 / 5}$，我们便 $O(1)$ 查询，$O(w ^ {4 / 5})$ 预处理时间复杂度解决了这个问题，由于预处理次数是 $O(n / B ^ 4)$，所以这里也是线性的。 综上所述，我们得到了一个单次操作复杂度 $O(\frac{\log n}{\log w} + \log w )$ 的数据结构，这里 **据说** 可以通过一些优化做到 $O(\frac{\log n}{\log w})$，但在这里由于我还没看所以暂时不做介绍。 ## 6. 一些拓展 如果我们允许下列中的一个： 1. 放松线性空间的限制 2. 保留线性空间的限制，但是使用随机化和整数除法 那么我们可以得到一个 $O(\sqrt{\log n})$ 的动态搜索的时间复杂度上界。 当 $n$ 超过 $2 ^ {\frac{(\log w) ^ 2}{36}}$ 时（这里 $\frac{1}{36}$ 的常数是论文中给出的，由于我的部分细节和论文中不同，可能是不同的常数）， 对于 1 的 case，可以通过使用 vEB 树来实现，对于 2 的 case，可以通过使用 Y-fast trie 实现。 对于这样的 $n$，这两个数据结构可以在 $O(\log \log U) = O(\log w) = O(\sqrt{\log n})$ 的时间完成一次搜索操作。 当 $n$ 小于这个数时， 对于较小的 $n$，我们使用 fusion tree，通过调节 $B = \Theta(2 ^ {\sqrt{\log n}})$。 在这个 $B$ 下，我们的时间复杂度是 $O(\frac{\log n}{\log B} + \log B) = O(\sqrt{\log n})$。 综上所述，如果引入随机化和整数除法，可以 $O(n \sqrt{\log n})$ 时间，线性空间整数排序。 ## 7. 总结 由信息论可以证明基于比较的排序下界是 $\Omega(n \log n)$ 的，但整数排序其实是非常复杂的一个问题，还有待研究。

魔法森林里有一颗大树，下面经常有小孩召开法。 大树可以看做一个有 $n$ 个节点，$n - 1$ 条边的无向连通图。大树的每个节点都有若干瓶矿泉水，初始第 $i$ 个节点有 $a_i$ 瓶矿泉水。 麦杰斯住在大树顶端，有一天他想改造一下大树，方便他巨大多喝水之后可以垃圾分类矿泉水瓶。 麦杰斯喜欢二进制运算，所以他会有以下三种操作： 1. 将树上与一个节点 $x$ 距离为 $1$ 的节点上的矿泉水数量 $+1$。这里树上两点间的距离定义为从一点出发到另外一点的最短路径上边的条数。 2. 在一个节点 $x$ 上喝掉 $v$ 瓶水。 3. 询问树上与一个节点 $x$ 距离为 $1$ 的所有节点上的矿泉水数量的异或和。 麦杰斯共有 $m$ 次操作，他希望你在每次 $3$ 操作后告诉他答案。

第一行两个正整数 $n,m$，分别表示树的节点个数和麦杰斯的询问个数。 第二行到第 $n$ 行，每行两个整数表示有一条连接这两个节点的边。 第 $n + 1$ 行 $n$ 个整数，第 $i$ 个整数表示初始第 $i$ 个节点上的矿泉水数量。 第 $n + 2$ 行到第 $n + m + 1$ 行，每行先读入一个整数 $opt$ 表示操作类型。 如果 $opt = 1$ 或 $3$ ，接下来读入一个整数 $x$ 表示麦杰斯操作的节点标号。 否则接下来读入两个整数 $x, v$ 表示麦杰斯操作的节点标号和他喝的水的数量。

对于每一个 $3$ 操作，输出一行一个整数表示答案。

Idea：dangxingyu，Solution：dangxingyu，Code：dangxingyu，Data：dangxingyu 对于 $30\%$ 的数据，满足 $n \le 10^3$，$m\le 10^3$。 对于 $60\%$ 的数据，满足 $n \le 10^5$，$m \le 10^5$。 对于另外 $10\%$ 的数据，存在一个点满足所有点到该节点的距离 $\le 1$。 对于 $100\%$ 的数据，满足 $1\le n \le 5\times 10^5$，$1\le m \le 5\times 10^5$，$0\le a_i \le 10^5$，$1 \le x \le n$，$opt\in\{1,2,3\}$。 保证任意时刻每个节点的矿泉水数非负。 温馨提示：矿泉水瓶不是干垃圾也不是湿垃圾，而是可回收垃圾。