猫树
引入
ST 表的复杂度非常优秀，$O(n\log n)$ 预处理，$O(1)$ 查询。但是只能维护可重复贡献的信息（如 $\min,\max$，按位与，按位或）。而很多时候我们维护的信息只满足结合律，只能用线段树维护。
而猫树以同样的复杂度，却可以维护仅满足结合律的信息。
算法简介
猫树基于线段树的思想，能 $O(n\log n)$ 预处理，$O(1)$ 查询支持结合律和快速合并的信息。空间复杂度 $O(n\log n)$。
具体来说，对于一个询问区间 $[L,R]$，若 $l=r$，可以直接得出答案。否则考虑在线段树上查询它的过程中，若它不是线段树上的某个完整区间，那么必然存在一个结点 $p$，在这个结点上同时访问左右两个儿子。若它恰好是线段树上的某个完整区间，那么视该节点为 $p$，且同时访问该结点的左右两儿子。
这样就能把某区间的贡献拆成 $[L,mid],[mid+1,R]$ 两部分。且 $[L,mid]$ 恰好是上文中 $p$ 的左儿子的一段后缀，$[mid+1,R]$ 是右儿子的一段前缀。那么我们可以 $O(n\log n)$ 地预处理线段树每个结点前后缀的信息。容易发现每一层前后缀信息都恰好有 $n$ 个，在找到 $p$ 的层数后就能 $O(T)$ 求解，其中 $T$ 为合并信息的复杂度，通常为 $O(1)$。
但是如何找到 $p$ 的层数呢？在一般的线段树上貌似只能 $O(\log n)$ 求解。这时候我们或许可以试着考虑一下 zkw 线段树，找到对应叶子结点后容易发现 $p$ 就是 $\mathrm{lca}$，那么树剖或倍增可以 $O(\log\log n)$ 找到 $p$ 后求解层数。用 RMQ+欧拉序可以 $O(1)$。
但这真的是我们想要的答案吗？
如果你熟悉 zkw 线段树，容易发现结点 $u$ 的父亲是 $\left\lfloor\frac{u}{2}\right\rfloor$，即二进制下右移一位。那么在这种情况下 $\mathrm{lca}(l,r)$ 是多少呢？由于满二叉树下所有叶子结点深度相同，那么我们考虑同时右移。容易发现，$\mathrm{lca}(l,r)$ 恰好就是 $l,r$ 二进制下相同的一段前缀。那么其实 $\mathrm{lca}(l,r)$ 的层数就是 $\log_2((l+2^k)\oplus (r+2^k))$，其中 $\oplus$ 表示按位异或，$2^k$ 是大于 $n$ 的最小 $2$ 的次方数。那么其实它还可以再简化一下，因为 $2^k\oplus 2^k=0$，故 $p$ 的层数就是 $\log_2(l\oplus r)$。