猫树

yuanzhiteng · 2023-09-17 22:42:16 · 个人记录

一. 猫树是什么

猫树名字的由来

为什么叫猫树呢，因为这棵树像猫一样可爱。

不扯了，猫树其实最早由猫锟提出，所以得名猫树。

猫树的作用

众所周知，线段树能够以 \mathcal{O}(\log n) 的时间复杂度建树以及查询区间信息。

但是如果区间信息是像线性基这样合并是 \mathcal{O}(\log ^2 w) 的呢？

那查询的总时间复杂度就变成了 \mathcal{O}(q\log n\log ^2 w) 了，q 小一点还好，但是如果 q 很大呢？

所以我们想让它的查询变得更快。

于是猫树孕育而生。

猫树支持 \mathcal{O}(n\log n) 的预处理基础下 \mathcal{O}(1) 回答每次询问，但不支持修改操作。

这里的 \mathcal{O}(1) 指的是 \mathcal{O}(1) 次合并，对于线性基便是 \mathcal{O}(\log ^2 w) 的。

二. 猫树如何实现

我们考虑这样一件事情：

以区间查询和为例，假设当前查询的区间为 [l,r]。

如果我们预处理过两个区间，且这两个区间可以合并成 [l,r]，那我们是不是就可以 \mathcal{O}(1) 回答询问了呢？

这便是猫树的核心思想。

预处理哪些区间，又如何预处理这些区间呢？

1. 对于当前处理的区间 [l.r]，我们首先将整个区间 [l,r] 分成 [l,mid] 和 [mid+1,r]。

2. 然后从 mid 出发，暴力更新 [i,mid],[mid+1,j](l\le i\le mid,mid+1\le j\le r) 的信息。
   比如对于区间和，那么对于左区间：f_i=f_{i+1}+a_i；右区间：f_i=f_{i-1}+a_i。

3. 按照上述方式递归地去更新 [l,mid] 和 [mid+1,r]，直到所有区间被更新完毕。

不难发现，预处理的时间复杂度是 \mathcal{O}(n\log n) 的。

预处理完后，有一个特别的性质：

对于任意一个查询区间 [l,r]，总会有一个预处理过的区间 [L,R] 使得 l \le mid=\dfrac{L+R}{2}\le r。

我们姑且叫这个 mid 为 [l,r] 的分割点。

比如：

其中红色点是我们查询的区间，绿色点便是分割点。

这样的话，便能用已经预处理过的 [l,mid] 和 [mid+1,r] 去 \mathcal{O}(1) 地回答询问了。

接下来的问题便是：如何快速找到分割点。

如果暴力找的话，显然是 \mathcal{O}(\log n) 的。

那这不就变成线段树了吗...甚至还不带修...

我们再仔细观察一下。

哎，分割点不就是 l,r 对应的叶子节点的 lca 吗！

如下图：

哎，那 lca 不就可以倍增 / 树剖求了吗。

这样单次询问的时间复杂度就被优化到了 \mathcal{O}(\log\log n)。

好像是比线段树强了。

桥豆麻袋，还可以更快！

接下来就是很神奇的想法了。

直接看这棵线段树可能发现不了什么。

但是如果这是一棵 满二叉树 呢？

我们会发现，i 和 j（线段树上的编号） 的 lca 为 i,j 在二进制下的最长公共前缀 LCP！

比如说上图中 12,13 的最长公共前缀 LCP(12,13)=LCP((1100)_ 2,(1101)_ 2)=(110)_ 2=6

而 6 恰好就是 12,13 的 lca 的编号！

所以我们只要想办法将 LCP 求出来即可。

我们记 bitlen_i 表示 i 在二进制下的长度（位数）。

不难知 bitlen_i=bitlen_{i>>1}+1，可以预处理出来。

知道这个有什么用呢？

延用上面的例子。

如果我们将 (1100)_ 2 \oplus (1101)_ 2=(1)_ 2，会发现它们的 LCP 正好异或抵消了。

并且异或后较异或前少的位数正好就是 LCP 的位数！（因为异或后最高位只可能是一个 1 一个 0 的情况，否则会成为 LCP）

而在满二叉树中编号（堆式建树）对应的二进制位数即为该节点所在的层数。

又因为是两个满二叉树中的叶子节点异或，所以它们的位数是相同的。

因此，LCP 所在的层数即为：

哎，不用求出编号吗？

笨蛋，在猫树中我们每一层预处理的时候存的是那一层的信息，所以只用知道 LCP 在哪一层就够了。

具体实现看代码。

需要注意的是，如果 n \neq 2^k，那么要通过新建叶子节点将其补全以确保其是一棵满二叉树。

这样，我们就建立了一棵 O(1) 回答单次询问的静态线段树——猫树。

三. 猫树的具体应用

【模板】ST 表

虽说是 ST 表的模板，可它也是猫树的模板。

猫树入门题，不多展开。

code

GSS1 - Can you answer these queries I

嗯，也是比较常见的猫树的应用。

不带修同时对单次询问复杂度有很高要求时可以往猫树上考虑。

题目要求静态区间最大子段和。

我们只用考虑如何预处理信息即可。

其实和线段树的思路差不多。

令 SegMaxsum_{d,i} 表示第 d 层猫树上 [i,mid]/[mid+1,i] 的区间最大子段和，Maxsum_{d,i} 是在 SegMaxsum_{d,i} 的基础上强制包含 a_{mid} 的最大子段和。

预处理是很好写的。

询问时假设 Lca\_deep=d，那么只需要返回 Max\{Max\{SegMaxsum_{d,l},SegMaxsum_{d,r}\},Maxsum_{d,l}+Maxsum_{d,r}\} 即可。

code

GSS5 - Can you answer these queries V