区间半群查询与 Ackermann 函数

最近在思考半在线卷积的复杂度有没有可能进一步优化, 决定先理清类似的问题以寻求经验.

一区间合并

如果询问的时候不能进行半群运算, 显然我们需要在预处理阶段处理所有答案, 必须进行 \(O(n^2)\) 次计算.

二区间合并

如果询问的时候可以进行一次半群运算, 则可以把序列每次在中点处折开, 处理中点到两边的信息, 然后剩下的递归下去.

这样预处理的时间是 \(O(n\log n)\), 询问只需要 \(1\) 次询问.

四区间合并

先把序列分成 \(n/\log n\) 个大小为 \(\log n\) 的块, 消耗 \(O(n)\) 的时间处理出每个块前缀和后缀的信息.

询问的时候, 如果端点在同一个块里, 则直接考虑子问题里的情况. 否则取两端块的前后缀信息, 拼上一个对块预处理的二区间结构. 这是个四区间合并.

由于我们现在是对一个 \(n/\log n\) 大小的数组做二区间合并的信息预处理, 时间是 \(O(n)\) 的, 然后要对每个小块递归下去, 所以时间复杂度是 \(T(n) = O(n) + (n/\log n) T(\log n)\). 也就是 \(n\) 乘以这个递归的深度, 即 \(O(n\log^* n)\).

查询只需要 \(3\) 次运算.

\(2k\) 区间合并

我们已经积累了足够的经验, 可以考虑攻克一般的 \(2k\) 了.

我们考虑定义 \(n = T(m, k)\) 是这样一个函数: \(n\) 是递归确定的数, 满足: 查询是 \(2k\) 区间合并的时候, 长度 \(\leq n\) 的数列可以只用 \(mn\) 次运算.

对于二区间合并而言, 分治一个 \(2^\ell\) 的数组, 在顶层需要消耗 \(2^\ell - 2\) 次运算. 总共的运算次数就是 \((\ell-2)2^\ell + 2 \leq (\ell - 1)2^\ell\), 我们可以取 \(n = 2^{m+1}\). 于是令

接下来考虑 \(2k\) 区间合并. 回忆我们的策略是把序列切成很多个块, 块形成的数列用 \(2(k-1)\) 区间合并的数据结构来做. 设 \(n = n'L'\), 其中 \(n'\) 是块形成的数列长度, 我们接受 \(L'\) 时间的预处理, 所以 \(n' = T(L', k-1)\). 但还需要前后缀的维护, 现在扫一层的时间是 \(3n\). 所以令 \(L' = T(m-3, k)\).

现在我们重新理一遍思路:

对于 \(n = n' L'\), 对于每个落在大小为 \(L'\) 的块, 我们给每个块分配 \((m-3)L'\) 的预处理时间, 所有块的预处理时间只和不超过 \((m-3)n\). 对于 \(n'\) 大小的块, 我们花了 \(2n'\) 时间预处理所有前后缀, 外加 \(n'L' = n\) 的时间预处理它的 \(2(k-1)\) 区间合并的结构.

于是我们有

最后补一下边界情况, 不妨直接让 \(T(0,k)=T(1,k)=T(2,k) = 2k\).

那么对于 \(n \leq T(m, k)\), 可以在 \(mn\) 次预处理的情况下支持每次查询 \(2k-1\) 次操作.

Ackermann 函数

不妨令 \(m = 3p\), 然后让 \(T\) 的输出缩小到 \(1/3\) 量级, 记为新的函数 \(S(p, k)\).

由于 \(T(3p, 1) = 2^{3p+1} \geq 2^{3p-1}\cdot 3\), 所以令 \(S(p, 1) = 2^{3p-1}\).

对于递归式, 由于 \(T(3p, k) \geq T(T(3p-3,k),k-1)\), 令 \(S(p,k) = S(S(p-1,k),k-1)\).

再对于 \(k\geq 2\), 令边界条件 \(S(0,k) = \lfloor 2k/3\rfloor\).

现在整理我们的定义:

\(S(p, 1) = 2^{3p-1}\).

\(S(0, k) = \lfloor 2k/3\rfloor\).

\(S(p,k) = S(S(p-1,k),k-1)\).

回顾 Ackermann 函数 \(A(m,n)\) 的定义:

\(A(0,n)=n+1\),

\(A(m+1,0) = A(m, 1)\),

\(A(m+1,n+1) = A(m, A(m+1,n))\).

只要证明存在 \(c\) 使得 \(S(cn,cn) > A(n,n)\), 就可以证明: \(n\) 次询问只需要 \(O(n\alpha(n))\) 次半群运算了.

(鸽)