高效处理无修改区间询问的方法

高效处理无修改区间询问的方法¶

问题描述¶

给出一个某种元素的序列\(a_1,a_2,\dots,a_n\)，要求进行\(m\)次询问，每一次是询问一段区间\([l,r]\)的某种支持结合律和快速合并的信息。

要求复杂度尽量优秀，假设合并复杂度为\(O(1)\)。

以下的时间复杂度\(O(A)+O(B)+O(C)\)表示预处理复杂度、单次询问的复杂度和空间复杂度。

各种性质的具体问题¶

可减信息，如区间和、区间异或和¶

直接用前缀和实现，复杂度\(O(n)+O(1)+O(n)\)。

可重复贡献信息，如区间最值¶

如果序列很长，使用线段树即可，复杂度\(O(n)+O(\log n)+O(n)\)。

如果询问很多，但序列不是特别长，可以用倍增的RMQ，复杂度\(O(n\log n)+O(1)+O(n\log n)\)。

如果序列很长，询问也很多，可以对序列线性建立笛卡尔树转为LCA问题，然后转为正负1RMQ，每\(\log n\)分一段打表预处理，复杂度\(O(n)+O(1)+O(n)\)。（这个还不是太懂）

仅满足支持结合律和快速合并，如最大子段和、区间的串哈希值¶

一般使用线段树实现，复杂度\(O(n)+O(\log n)+O(n)\)。

以上内容摘录自ImmortalCO。

对于第三类具体问题，询问的复杂度不够优秀，那么有什么解决方案呢？

离线¶

如果可以将询问离线，我们有一种基于分治的做法。考虑分治树的结构，每个节点代表一个区间\([L,R]\)。对于一个询问\([l,r]\)，我们可以找到分治树上一个最小的完全包含它的区间（具体实现可以\(O(1)\)求分治树上的LCA），把这个询问挂在对应的节点上。在分治到每个区间时，求出以分治中心\(mid\)为开头和结尾的信息，就可以\(O(1)\)处理挂在这个区间上的询问了。我们得到了一个预处理复杂度\(O(n\log n)\)，离线\(O(1)\)询问的做法。

实际上，这场的J题也是类似的思想，当时还想了好久。

在线¶

思想是相同的，但需要储存下预处理的信息，空间复杂度也是\(O(n\log n)\)。这个东西叫做猫树，本质上是记录下分治的过程。ImmortalCO在原文中的解释是考虑询问\([l,r]\)在线段树上定位的过程，是在哪个节点\(p\)中同时递归到左右两个儿子。仔细思考可以发现这跟分治的本质相同。

猫树的拓展¶

直接引用ImmortalCO原话：

考虑把猫树扩展到树上，以资磁快速的链上信息询问。我们对树进行点分治，预处理所有点到重心的信息（需要保存“包括中心”和“不包括重心”两种信息，如果有方向要求要专门考虑），这样同样能拆成两个已经预处理的信息的和。询问的时候，我们需要找出这条链上最上面的重心。对点分治建立点分树（把重心连成树），然后我们要找到的重心就是询问的链端点的 LCA，这可以用倍增 RMQ 来预处理。

~~写完才发现好像只是搬运了一下文章，自己没写什么内容，不过写都写了，还是发一下算了。~~