猫树是什么

· · 个人记录

猫树是什么

原来是这样啊，我已经完全理解了.jpg

为什么要猫树

我们都知道线段树可以在 \mathcal{O}(\log n) 的时间复杂度处理区间询问。但其实不够准确，应该是 \mathcal{O}(T(n)\log n)，其中 T(n) 是合并两个节点信息的时间复杂度，只不过很多情况下它是常数。

但也有不是常数的时候，比如矩阵乘法，线性基合并，背包合并等等。此时多乘一个 \log 可能会让时间复杂度爆炸，所以猫树就被创造出来了。它可以用来解决不带修的 \mathcal{O}(T(n)) 区间询问，建树的复杂度是 \mathcal{O}(n\log nT(n))。（看起来和线段树差不多，但当 n,q 不同阶的时候就不一样了。即使同阶常数也要小很多，而且这里的合并是加入单个元素，在有些时候比两个节点合并快）

猫树怎么搞

我们考虑在线段树结点上维护 [l,mid] 信息合并的后缀和，(mid,r] 信息合并的前缀和。这样的话，对于所有跨过 mid 的询问我们都可以在 \mathcal{O}(T(n)) 的时间复杂度内合并出我们需要的信息。

欸，那对于询问 l,r 我们怎么找在哪个节点处理呢。考虑 [l,l] 和 [r,r] 的 \rm lca 即可。求 \rm lca 可以直接 \mathcal{O}(\log n)，毕竟一般 T(n) 都要大于这个我们才会用猫树。如果实在要用 \mathcal{O}(1) 的卡常可以参考 OI wiki。

你们有没有发现一个问题，这样的话空间会稍微有点爆炸，所以我们还有一个做法。如果询问允许离线的话，我们就 \rm dfs 一遍整个线段树，在每个节点处理跨过当前节点的询问，并把剩下的丢到两边。这样不显式建树避免了 \rm lca，也不用把所有的都存下来。好像都叫这个方法猫树分治。

其实基本就没了。P6240 好吃的题目，丢个板子题。