猫树和 sqrt tree

猫树分治

一种常见 trick，就是在分治时维护区间的前缀和后缀信息，用左区间的后缀和右区间的前缀求出跨过 mid 的答案。

习题：

P6240 好吃的题目

P7482 不条理狂诗曲

P4755 Beautiful Pair

猫树

猫树可以 O(n\log n) 预处理，O(1) 查询，O(n\log n) 空间复杂度解决序列上在线区间查询问题。

和同样时空复杂度的 ST 表相比，猫树不需要信息满足可重复贡献，只需要满足可合并，因此适用范围更广。

和 ST 表一样，猫树不支持修改。实际上是支持的但是复杂度单次 O(n)。

注意猫树不能完全代替 ST 表。一道能用 ST 表，似乎不能用猫树的题目：P3295 [SCOI2016]萌萌哒，用到了 ST 表对于相同长度的区间拆出的小区间长度也相同的性质。

但是猫树时空常数都略大，而且码量也较大。

具体做法：

先猫树分治一遍求出所有分治区间的前后缀信息。

然后需要求出询问对应的区间（即最小的同时包含 l,r 的区间）。这里的方法和 immortalCO 的略有不同。

首先特判掉 l=r 的询问。

存储信息用 \log n 个长度为 n 的结构体 s_{i,j} 表示分治第 i 层 j 对应的信息。

然后像线段树一样给区间编号（左区间 2k，右区间 2k+1）。

分治到叶子结点区间 (i,i) 时记录区间编号 p_i。

对于询问 l,r，只需要求出 x=p_l,y=p_r 的 lca 的深度。

根据线段树编号的性质，x,y 的 lca 就是二进制的 lcp（高位在前，去掉前导零，比如 1101 和 0110 的 lcp 就是 110）。

首先不妨设 x>y，然后去掉 x 的最低的若干位使 x 和 y 位数相同。可以用 x>>=__lg(x)-__lg(y)。

然后 __lg(x>>__lg(x^y)+1) 就是所求深度（此处定义根节点深度为 0）。因为 x^y 的最高位是第一个 x 和 y 二进制不同的位置。x>>__lg(x^y)+1 就是 x 和 y 的 lcp。

代码实现中可以预处理 lg 数组表示 __lg(x)+1。

如果允许离线，可以在分治过程中求出答案，空间复杂度优化到 O(n)。

习题：

CF750E New Year and Old Subsequence

SP1043 GSS1 - Can you answer these queries I

SP2916 GSS5 - Can you answer these queries V

P3246 [HNOI2016]序列 加强版 题解

树上猫树分治

其实就是点分治/边分治，不会的可以看树分治总结。

树上猫树

树链询问，无修改，强制在线。

考虑建出点分树，那么询问 (x,y) 对应的分治中心就是 x,y 在点分树上的 lca，可以用 rmq O(1) 求出。

点分治时求出两种信息，一种是分治范围内任意点到分治中心，一种是分治中心到任意点。两种信息中一种包含分治中心，一种不包含。用这两种信息合并就可以 O(1) 回答询问。

边分树同理不再赘述。

时空复杂度和序列猫树一样。

暂时没有找到习题，有好题推荐可以在评论区回复。

参考：一种高效处理无修改区间或树上询问的数据结构（附代码）（immortalCO）

sqrt tree

sqrt tree 可以 O(n\log\log n) 预处理，O(1) 查询。

适用范围和猫树相同，即维护区间半群（满足结合律的信息）。

首先对原序列取 \sqrt n 为块长分块。

对每一块，预处理块内前后缀信息。

对于块 i,j 预处理第 i 个块到第 j 个块的答案。

这样就可以回答跨块的询问。

对于块内的询问，考虑递归分块。

对 \sqrt n 个块继续取 \sqrt{\sqrt n} 为块长分块。

这样递归下去直到块长为 1 或 2。

容易发现只会递归 O(\log\log n) 层，每层预处理 O(n)，时间复杂度 O(n\log\log n)。

参考：OI Wiki sqrt tree