猫树
引入
ST 表的复杂度非常优秀,\(O(n\log n)\) 预处理,\(O(1)\) 查询。但是只能维护可重复贡献的信息(如 \(\min,\max\),按位与,按位或)。而很多时候我们维护的信息只满足结合律,只能用线段树维护。
而猫树以同样的复杂度,却可以维护仅满足结合律的信息。
算法简介
猫树基于线段树的思想,能 \(O(n\log n)\) 预处理,\(O(1)\) 查询支持结合律和快速合并的信息。空间复杂度 \(O(n\log n)\)。
具体来说,对于一个询问区间 \([L,R]\),若 \(l=r\),可以直接得出答案。否则考虑在线段树上查询它的过程中,若它不是线段树上的某个完整区间,那么必然存在一个结点 \(p\),在这个结点上同时访问左右两个儿子。若它恰好是线段树上的某个完整区间,那么视该节点为 \(p\),且同时访问该结点的左右两儿子。
这样就能把某区间的贡献拆成 \([L,mid],[mid+1,R]\) 两部分。且 \([L,mid]\) 恰好是上文中 \(p\) 的左儿子的一段后缀,\([mid+1,R]\) 是右儿子的一段前缀。那么我们可以 \(O(n\log n)\) 地预处理线段树每个结点前后缀的信息。容易发现每一层前后缀信息都恰好有 \(n\) 个,在找到 \(p\) 的层数后就能 \(O(T)\) 求解,其中 \(T\) 为合并信息的复杂度,通常为 \(O(1)\)。
但是如何找到 \(p\) 的层数呢?在一般的线段树上貌似只能 \(O(\log n)\) 求解。这时候我们或许可以试着考虑一下 zkw 线段树,找到对应叶子结点后容易发现 \(p\) 就是 \(\mathrm{lca}\),那么树剖或倍增可以 \(O(\log\log n)\) 找到 \(p\) 后求解层数。用 RMQ+欧拉序可以 \(O(1)\)。
但这真的是我们想要的答案吗?
如果你熟悉 zkw 线段树,容易发现结点 \(u\) 的父亲是 \(\left\lfloor\frac{u}{2}\right\rfloor\),即二进制下右移一位。那么在这种情况下 \(\mathrm{lca}(l,r)\) 是多少呢?由于满二叉树下所有叶子结点深度相同,那么我们考虑同时右移。容易发现,\(\mathrm{lca}(l,r)\) 恰好就是 \(l,r\) 二进制下相同的一段前缀。那么其实 \(\mathrm{lca}(l,r)\) 的层数就是 \(\log_2((l+2^k)\oplus (r+2^k))\),其中 \(\oplus\) 表示按位异或,\(2^k\) 是大于 \(n\) 的最小 \(2\) 的次方数。那么其实它还可以再简化一下,因为 \(2^k\oplus 2^k=0\),故 \(p\) 的层数就是 \(\log_2(l\oplus r)\)。