猫树

引入

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

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

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

而所谓「猫树」就是一种不支持修改，仅仅支持快速区间询问的一种静态线段树。

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

在处理线性基这样特殊的信息的时候甚至可以将复杂度降至 $O(n\log^2{w})$ 。

原理

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

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

有了这两个性质，我们就可以将询问的复杂度降至了。

实现

具体来讲我们建树的时候对于线段树树上的一个节点，设它代表的区间为。

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

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

下面是最关键的询问了。

如果我们询问的区间是那么我们把代表的节点和代表的节点的 LCA 求出来，记为。

根据刚才的两个性质，在所包含的区间之内并且一定跨越了的中点。

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

而这个过程仅仅需要次合并操作！

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

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

堆式建树

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

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

稍作思考即可发现发现在和的二进制下 lcp(x,y)=x>>log[x^y]。

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

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

由于建树的时候涉及到求前缀和和求后缀和，所以对于线性基这种虽然合并是 $O(\log^2{w})$ 但是求前缀和却是 $O(n\log{n})$ 的信息，使用猫树可以将静态区间线性基从 $O(n\log^2{w}+m\log^2{w}\log{n})$ 优化至 $O(n\log{n}\log{w}+m\log^2{w})$ 的复杂度。

参考

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.

本页面最近更新：2025/4/7 00:24:17，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：billchenchina, c-forrest, 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, luoguojie, Marcythm, megakite, Menci, moon-dim, NachtgeistW, onelittlechildawa, orzAtalod, ouuan, shadowice1984, shawlleyw, shuzhouliu, StudyingFather, SukkaW, Tiphereth-A, wy-luke, x2e6, Xeonacid, Ycrpro, yifan0305, zeningc
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用