猫树

引入

众所周知线段树可以支持高速查询某一段区间的信息和，比如区间最大子段和，区间和，区间矩阵的连乘积等等．

但是有一个问题在于普通线段树的区间询问在某些毒瘤的眼里可能还是有些慢了．

简单来说就是线段树建树的时候需要做 $O (n)$ 次合并操作，而每一次区间询问需要做 $O (\log n)$ 次合并操作，询问区间和这种东西的时候还可以忍受，但是当我们需要询问区间矩阵乘法这种合并（即一次矩阵乘法）复杂度高达 $O (k^{3})$ 的信息的话，此时就算是做 $O (\log n)$ 次合并有些时候在时间上也是不可接受的．

而所谓「猫树」就是一种不支持修改，仅仅支持快速区间询问的一种静态线段树．在询问次数较多（ $m = Ω (n)$ ）时，该做法才有显著价值．

构造一棵这样的静态线段树需要 $O (n \log n)$ 次合并操作，但是此时的查询复杂度被加速至 $O (1)$ 次合并操作．

在处理矩阵乘法这样合并代价高昂的信息的时候，使用猫树可以将单次查询复杂度从 $O (k^{3} \log n)$ 降至 $O (k^{3})$ ．

注意，在处理静态区间线性基查询这个问题上，虽然猫树可以优化普通线段树实现的区间线性基的复杂度，但有一种时空复杂度都更优的做法：前缀线性基．而且普通线段树可以处理动态区间线性基问题，但对于静态区间线性基查询，猫树不仅实现较为复杂，不是最优解，在功能上也没有差别．

原理

在查询 $[l, r]$ 这段区间的信息和的时候，将线段树树上代表 $[l, l]$ 的节点和代表 $[r, r]$ 这段区间的节点在线段树上的 LCA 求出来，设这个节点 $p$ 代表的区间为 $[L, R]$ ，我们会发现一些非常有趣的性质：

$[L, R]$ 这个区间一定包含 $[l, r]$ ．显然，因为它既是 $l$ 的祖先又是 $r$ 的祖先．
$[l, r]$ 这个区间一定跨越 $[L, R]$ 的中点．由于 $p$ 是 $l$ 和 $r$ 的 LCA，这意味着 $p$ 的左儿子是 $l$ 的祖先而不是 $r$ 的祖先， $p$ 的右儿子是 $r$ 的祖先而不是 $l$ 的祖先．因此， $l$ 一定在 $[L, mid]$ 这个区间内， $r$ 一定在 $(mid, R]$ 这个区间内．

有了这两个性质，我们就可以将询问的复杂度降至 $O (1)$ 了．

实现

具体来讲我们建树的时候对于线段树树上的一个节点，设它代表的区间为 $(l, r]$ ．

不同于传统线段树在这个节点里只保留 $[l, r]$ 的和，我们在这个节点里面额外保存 $(l, mid]$ 的后缀和数组和 $(mid, r]$ 的前缀和数组．

这样的话建树的复杂度为 $T (n) = 2 T (n / 2) + O (n) = O (n \log n)$ 同理空间复杂度也从原来的 $O (n)$ 变成了 $O (n \log n)$ ．

下面是最关键的询问了．

如果我们询问的区间是 $[l, r]$ 那么我们把代表 $[l, l]$ 的节点和代表 $[r, r]$ 的节点的 LCA 求出来，记为 $p$ ．

根据刚才的两个性质， $l, r$ 在 $p$ 所包含的区间之内并且一定跨越了 $p$ 的中点．

这意味这一个非常关键的事实是我们可以使用 $p$ 里面的前缀和数组和后缀和数组，将 $[l, r]$ 拆成 $[l, mid] + (mid, r]$ 从而拼出来 $[l, r]$ 这个区间．

而这个过程仅仅需要 $O (1)$ 次合并操作！

不过我们好像忽略了点什么？

似乎求 LCA 的复杂度似乎还不是 $O (1)$ ，暴力求是 $O (\log n)$ 的，倍增法则是 $O (\log \log n)$ 的，转 ST 表的代价又太大……

堆式建树

具体来将我们将这个序列补成 $2$ 的整次幂，然后建线段树．

此时我们发现线段树上两个节点的 LCA 编号，就是两个节点二进制编号的最长公共前缀 LCP．

稍作思考即可发现在 $x$ 和 $y$ 的二进制下 lcp(x,y)=x>>digits[x^y]．（其中 digits[x] 表示二进制下 $x$ 的位数，即 $⌊ \log_{2} x ⌋ + 1$ ）

所以我们预处理一个 digits 数组即可轻松完成求 LCA 的工作．

这样我们就构建了一个猫树．

由于建树的时候涉及到求前缀和和求后缀和，所以对于矩阵乘法这种合并复杂度为 $O (k^{3})$ 的信息，建树复杂度为 $O (n \log n \cdot k^{3})$ ．在此基础上，猫树将静态区间矩阵乘法查询的单次复杂度从 $O (k^{3} \log n)$ 降至 $O (k^{3})$ ，从而在询问次数较多（ $m = Ω (n)$ ）时，将处理 $m$ 次查询的总复杂度从 $O (n \cdot k^{3} + m \cdot k^{3} \log n)$ 优化至 $O (n \log n \cdot k^{3} + m \cdot k^{3})$ ．

参考

immortalCO 的博客
[Kle77] V. Klee, "Can the Measure of be Computed in Less than O (n log n) Steps?," Am. Math. Mon., vol. 84, no. 4, pp. 284–285, Apr. 1977.
[BeW80] Bentley and Wood, "An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles," IEEE Trans. Comput., vol. C–29, no. 7, pp. 571–577, Jul. 1980.

本页面最近更新：2026/9/10 22:16:13，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, c-forrest, hcx2012Git, karsl-program, billchenchina, CCXXXI, chenryang, chenzheAya, Chrogeek, ChungZH, CJSoft, cjsoft, countercurrent-time, DawnMagnet, Early0v0, Enter-tainer, ethan-enhe, GavinZhengOI, Haohu Shen, Henry-ZHR, HeRaNO, hjsjhn, hly1204, hsfzLZH1, iamtwz, Ir1d, jaxvanyang, Jebearssica, kenlig, konnyakuxzy, ksyx, lailai0916, luoguojie, Marcythm, megakite, Menci, moon-dim, NachtgeistW, onelittlechildawa, orzAtalod, ouuan, shadowice1984, shawlleyw, shuzhouliu, StudyingFather, SukkaW, wy-luke, x2e6, Xeonacid, Ycrpro, yifan0305, zeningc
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用