猫树瞎写

处理一类静态区间查询的问题，优势是快速合并

先引入一个例子：区间求和

普及组的小朋友应该都知道这个可以用前缀和+差分处理

然后是 RMQ

也许这东西确实有更低复杂度的做法，但是我们想想能不能也用前缀和类似的方法

这东西的问题在于没法差分

但是众所周知不能减就可以只加不减，和回滚莫队一样

因此类似回滚莫队，选若干个关键点，然后向两边扩展，整一个前缀/后缀最值的数组

不难发现我们选完关键点后，关键点也并不能扩展到整个序列，因此每一个关键点还只能对应一个区间

那么对于一次询问 $[l, r]$ ，我们要找到一个关键点，使得这个关键点对应的区间包含 $[l, r]$ 且这个关键点被 $[l, r]$ 包含

考虑总得有一个区间是 $[1, n]$ ，不难发现若不经过关键点则可以分治下去

因此考虑建一棵线段树，区间就是对应区间，然后中点就是关键点

发现这样每一层都是 $O(n)$ 的，因此预处理是 $O(n\log n)$

然后现在就是要找关键点了

相当于不难发现对于 $[l, r]$ ，其端点对应的两个结点的 LCA 的关键点一定在 $[l, r]$ 间且该区间一定包含 $[l, r]$

因此现在要快速求 LCA

当然你可以 $O(\log n)$ 暴力跳，甚至可以 $O(\log\log n)$ 倍增

不过你还可以堆式建树

具体来说，我们建线段树的时候一个点的两个儿子是 rt * 2, rt * 2 + 1

我们发现把最后一层补满之后，这就是一棵完全二叉树，并且可以根据结点编号的 $\log$ 来判断在哪一层，或者具体一点，二进制下长度相同

我们还发现一个点父亲的编号一定是它的一段前缀

因此我们现在要求两个长度相同二进制数的 LCP

直接异或一下就能求出 LCP 长度，然后直接右移即可

这样就能 $O(1)$ 查询了

---

这东西暂时看起来意义不明

不过我们实操中有些东西不能 $O(1)$ 合并

发现猫树的合并次数是 $O(n\log n)-O(1)$ 的

因此在合并难度大的一些题目中会有用

最典型就是线性基

---

猫树的单点修改显然是 $O(n)$ 的

不难理解，每一层都是一个结点，然后每过一层规模减半，最后还是 $O(n)$

考虑区间修改，例如区间加然后 RMQ

洛谷的猫树日报中说是 $O(n\log n)$ 的，因为要重构

不过我个人觉得，如果能打标记的话应该是可以 $O(n)$ 的

这里要是错了就赶紧来喷我

考虑对于被完整修改的结点我们打标记

不能完整修改的结点每一层最多两个，也是 $O(1)$

因此还是 $O(n)$

---

猫树可以用在序列长度短的题目中

不过仔细想想，那个 $O(n)-O(1)$ RMQ 也挺够用的

再仔细想想，这东西再 RMQ 上其实和 ST表差别也不大

所以估计正式比赛中没什么用（（