有的时候线段树还是太慢了（需要 \(\log\) 次合并得出答案）。使用猫树可以空间换时间：\(O(n\log n)\) 空间，\(O(1)\) 时间。但是猫树不支持修改。
应用条件：静态，卡时间死/合并复杂度很高。
【构建】
先建出一颗正常的线段树。同时对于 \([l,r]\)，我们预处理 \([l,mid-1]\) 的后缀信息和 \([mid,r]\) 的前缀信息（具体视题目而定）。于是我们就得到了一颗猫树。因为对每个区间都要记录 \(O(len)\) 个信息，所以一层记录 \(O(n)\)，空间复杂度 \(O(n\log n)\)。
在询问 \([l,r]\) 时，我们找到叶结点 \([l,l]\) 和 \([r,r]\) 在线段树上的 LCA，记作 \(p\)。显然 \([l,r]\) 包含 \(p\) 对应区间的 \(mid\)。那么我们使用在 \(p\) 处记录的前后缀拼起来就能得到 \([l,r]\) 的信息了！这样只需要 \(O(1)\) 次合并即可得出答案。
但是还有一个问题：找 LCA 怎么找？暴力是 \(O(\log n)\)，倍增是 \(O(\log\log n)\) 的。都不太优美。
这里有一个很牛的技巧：堆式建树。添加一些无用元素，把 \(n\) 拓展到 \(2\) 的幂，此时建出的线段树一定呈现满二叉树的形态。按堆的方式给每个结点编号，我们发现编号 \(x,y\) 的 LCA 编号就是二进制下 \(x,y\) 的最长公共前缀！（可以这么理解：二进制上一个 \(0\) 表示去往左儿子）
所以 LCA 编号就是 x >> log2[x ^ y]，这样就能 \(O(1)\) 求 LCA 啦！
【例题】
不同题目的区别主要在于每个结点记录什么前后缀信息。
【区间最大子段和】
SP1043 GSS1
求区间最大子段和。
前后缀记录 "最大子段和"、"最大后缀"、"最大前缀" 即可。
【区间 01 背包】
P6240 好吃的题目
有 \(n\) 个物品，重量 \(\le 200\)。多次询问：取出 \([l,r]\) 内物品、容量为 \(k(\le 200)\) 的最大价值。
\(n\le 4\times 10^4,q\le 2\times 10^5\)。
前后缀记录 "该前/后缀容量为 \(v\) 的最大价值"。记录的空间复杂度 \(O(200\cdot n\log n)\)。
询问时枚举给前缀用多少容量和后缀用多少容量。复杂度 \(O(200\cdot q)\)。