跳转至

猫树

引入

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

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

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

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

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

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

原理

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

  1. \([L,R]\) 这个区间一定包含 \([l,r]\)。显然，因为它既是 \(l\) 的祖先又是 \(r\) 的祖先。

  2. \([l,r]\) 这个区间一定跨越 \([L,R]\) 的中点。由于 \(p\) 是 \(l\) 和 \(r\) 的 LCA，这意味着 \(p\) 的左儿子是 \(l\) 的祖先而不是 \(r\) 的祖先，\(p\) 的右儿子是 \(r\) 的祖先而不是 \(l\) 的祖先。因此，\(l\) 一定在 \([L,\mathit{mid}]\) 这个区间内，\(r\) 一定在 \((\mathit{mid},R]\) 这个区间内。

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

实现

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

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

这样的话建树的复杂度为 \(T(n)=2T(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,\mathit{mid}]+(\mathit{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>>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.