静态区间结合律信息查询&块的遗留科技

不出意外应该是把最后一步冲过去了...感谢开学典礼(雾) 对于标题，如果信息可以 $\Theta(1)$ 简单合并，那么存在 $\Theta((n+q)\alpha(n))$ 的做法. ------ ## -1 暴力 预处理所有区间的信息然后 $\Theta(1)$ 询问，复杂度 $\Theta(n^2)-\Theta(1)$. ## 0. 线段树上分治 建立线段树，对每个非叶节点 $[l,r]$ 的划分点 $mid$，预处理该区间内以 $mid$ 为结尾的所有后缀的信息和以 $mid+1$ 开头的所有前缀的信息. 每个节点贡献复杂度 $\Theta(len)$，总复杂度 $\Theta(n\log n)$. 对于询问，定位到该询问将要被拆分成两部分的区间，$\Theta(1)$ 合并预处理的信息. 定位的过程相当于求 $lca$，那么可以用四毛子做到总复杂度 $\Theta(n\log n)-\Theta(1)$ ## 0.5 Sqrt tree 虽然 lxl 把这个名字批判了一番，但先叫这个吧( 虽然和接下去的优化没有什么复杂度上的关联，但具有启发性(可能). 把区间按照 $\sqrt n$ 分块，对于跨块的查询，我们使用 **-1** 中的方法处理块间的信息，并预处理每个块的前后缀信息，复杂度 $\Theta(n)$；对于块内的查询，递归下去进行. 那么子问题的规模每次会变成 $\sqrt{n}$，进行 $\Theta(\log\log n)$ 次递归就会变为 $\Theta(1)$，复杂度 $\Theta(n\log\log n)$. 定位同样在求lca，可以 $O(1)$ 查询 ## 1. ??? 我愿称之为窦树(雾) 发现在 **0.5** 中块间信息并没有必要用 $\Theta(n^2)$ 的做法去做，本质上还是一个规模为 $\Theta(n/B)$ 的区间查询问题. 那么我们考虑按照 $\log n$ 分块，对于跨块的询问，使用 **0** 的做法维护块间信息，块内的询问递归下去. 那么问题规模每次变为 $\Theta(\log n)$，最多 $\Theta(\log^* n)$ 就会变成 $\Theta(1)$，那么树深度 $\Theta(\log^* n)$，总复杂度 $n\log^* n+q$. ## ???. ??? 发现这个复杂度甚至可以迭代！设上一层数据结构的树深度为 $T(m-1,n)$，那么按照 $T(m-1,n)$ 分块，块间信息用上一层数据结构维护，块内递归下去. 那么这一层数据结构的树深度就是每次把 $n$ 变成 $T(m-1,n)$ 直到 $n=\Theta(1)$ 的次数. 稍微手玩一下可以发现，$m=1$ 时就是 $\log^* n$，$m=2$ 时就是对 $n$ 不停取 $\log^*$ 直到 $n=\Theta(1)$ 的次数，以此类推. 这个东西的复杂度随 $m$ 增大下降得非常快，我们找到最小的满足 $T(m,n)=\Theta(1)$ 的 $m$，那么来计算此时的复杂度. 经过查表可以发现，$m$ 就是反阿克曼函数 $\alpha(n)$. 考虑询问复杂度，每次需要花费 $\Theta(1)$ 时间进入上一层数据结构，那么询问复杂度 $\Theta(\alpha(n))$. 预处理时，第 $m$ 层需要花费 $\Theta(nT(m,n))$ 的时空复杂度进入到规模为 $\Theta(nT(m,n)/T(m-1,n))$ 的下一层数据结构，因此预处理的时空复杂度为 $\Theta(n\alpha(n))$，总复杂度 $\Theta((n+q)\alpha(n))$ 好像已经达到下界了？ ----- 下面是与之无关的一个东西，也是非常规分块的一个例子，是[块](https://www.luogu.com.cn/user/66965)介绍给我的. 除此之外，sqrt tree 也是块独立发现并介绍给我的. 由于块已经退役了，这成为了宝贵的文化遗产(雾). 使用区间加区间求和为例子. 考虑不使用 $\sqrt n$ 分块而是先按 $n^{2/3}$ 分块，分出的块称为大块，对每个大块再按 $n^{1/3}$ 分块，分出的块称为小块. 这样形成一个三层的分治结构. 那么考虑一次提取区间，必然是形如 若干散点-若干小块-若干大块-若干小块-若干散点 的东西的一个部分，每个“若干”的数量为 $O(n^{1/3})$. 每个节点维护标记，下传需要 $O(n^{1/3})$ 的时间，每次修改只会涉及到 $\Theta(1)$ 个节点下传标记，那么询问和修改的复杂度都为 $n^{1/3}$ . 当然也可以把 $3$ 换成别的东西，做到 $O(xn^{1/x})$. 到这里并没有什么用，但当查询和修改不平衡时，这个东西可以做到用 $O(xn^{1/x})$ 完成其中一个，用 $O(x)$ 的复杂度完成另一个. 举例，如果有 $O(n)$ 次单点修改 $O(n\log n)$ 次区间求和，那么可以做到 $O(nxn^{1/x})$ 复杂度修改 $O(xn\log n)$ 查询，解一下就得到 $x=\log n/\log\log n$，这时复杂度为 $O(n\log^2 n/\log\log n)$. ---- upd 折腾了一番搞到了论文，大概看了一下发现确实是对的(虽然复杂度毛估估),也确实是下界.