菜王的 blog

线段树已经可以使用 $O(\log n)$ 次信息合并来查询一段区间内的信息，正常情况下这已经足够快了。

但是，当合并信息的时间复杂度过高（线性基的 $O(\log^2 w)$）时，这个信息合并次数还是不可接受的，因此就有了猫树。

猫树不支持修改，且建树需要 $O(n \log n)$ 次信息合并，但是可以做到单次查询只需 $O(1)$ 次信息合并。

思想

我们考虑一次线段树上的区间查询，比如对这棵 $[1, 8]$ 的线段树进行 $[1, 3]$ 的区间查询，它在线段树上可以表示成这样：

我们考虑这个区间被分成两半时所在的节点（在这里就是 $[1, 4]$ 区间所对应的节点），我们查询的区间被节点对应的区间中点分成了两半，为一个前缀和一个后缀。

如果我们能够对于每一个节点预处理出 $[l, mid]$ 的所有后缀信息，以及 $(mid, r]$ 的所有前缀信息，我们只需要对于每个询问区间快速找到对应的划分节点，并合并对应的前缀信息以及后缀信息即可。

预处理出信息是简单的，直接对每个区间从 $mid$ 递推过去即可。而我们可以发现，划分节点就是线段树上 $l$ 所在的叶节点与 $r$ 所在的叶节点的 LCA，所以我们可以在 $O(\log \log n)$ 的时间复杂度内求出划分节点。

但这还不够，我们考虑更多性质。当 $n$ 为 $2$ 的整数次幂的时候，线段树上两个节点的 LCA，就是两个节点二进制编号的 LCP。接下来可以发现 lcp(x, y) = x >> Lg2[x ^ y] + 1（Lg2[1] = 0），于是我们只需预处理出 Lg2 即可 $O(1)$ 求 LCA。

另外，对于线性基这种插入只需 $O(\log w)$ 但是合并要 $O(\log^2 w)$ 的信息，预处理的时间复杂度为 $O(n \log n \log w)$ 而并非 $O(n \log n \log^2 w)$，所以用猫树做静态区间线性基是两只 $\log$ 而非三只。

分治

如果维护的信息空间是 $O(1)$ 的，那么猫树的空间复杂度为 $O(n \log n)$，并非线段树的线性，不排除被卡空间的可能（点名批评 command_block，猫树板子题还卡空间）。

我们可以不显性建出猫树，只把询问挂在对应的 LCA 上，最后在线段树上 DFS，只维护当前节点的前后缀信息。

于是这样的空间复杂度变成了线性，但是不能在线回答询问，我们称之为猫树分治。

例题

Ivan and Burgers

好吃的题目

[Ynoi2009] rprmq1