P13698 强制在线复杂度下界的一个归约证明

· · 个人记录

OMv(Online Matrix–Vector multiplication)猜想：

给定布尔矩阵 M \in \{0,1\}^{n\times n}，接下来会收到 n 个 n 维布尔向量 v^{(1)},\dots,v^{(n)}，在线回答

Mv^{(t)}

的结果，这里将矩阵乘法定义中的 + 换为 \vee，\times 换为 \wedge。

对于上述 OMv 问题，不存在一个算法能在 O(n^{3-\epsilon}) 时间内解决。

目前还没有找到一个这样算法或是证明猜想成立。

以下证明仅能得到强制在线回答中位数时的一个复杂度下界 \widetilde{O}(n^{1.5})，笔者水平有限，还未得到一个高于 \widetilde{O}(n) 的可离线版本的复杂度下界。

我们考虑树是一条链，即在一个给定序列 a_i 上操作，查询换为给定 m，验证其是否为当前的中位数，这个问题显然要更弱。

沿用上面描述 OMv 问题时的记号，考虑任意一个规模为 \sqrt{n} 的 OMv 问题。初始令 a = \{\}，先枚举 M 的每一列 j，再枚举每一行 i，当 m_{i,j}=1 时，向 a 最后加入一个数 i。最终得到长度不超过 n 的序列 a。记第 j 列加入的元素为 a_{l_j,\dots,r_j}。

要查询 Mv^{(t)} 时，从 1 到 \sqrt{n} 枚举 j，当 v^{(t)}_j=1 时，说明 M 的第 j 列会对答案造成贡献，此时将 a_{l_j,\dots,r_j} 加入 D 中一次。最后我们想知道对于每个行编号 i，i 在 a 中的出现次数有没有增加。

由于有强制在线，只需要在 a 中额外加一个 0 和 n+1，通过填充 0 和 \sqrt{n}+1 的个数可以一次询问求出序列中 \le i 的数是否至少有 c 个，然后即可二分求出当前序列中一个数 i 的出现次数。

这样修改和询问都是 \widetilde{O}(n) 级别的，如果存在一个 \widetilde{O}(n^{1.5-\epsilon}) 时间内解决中位数查询问题的算法，则有 OMv 猜想不成立。因此该问题目前的一个复杂度下界为 \widetilde{O}(n^{1.5})

将 (i,a_i) 看作二维平面上一个点，我们的修改是将矩形 [l,r]\times (-\infty,+\infty) 内所有点权值 +k，查询使用二分答案，求矩形 (-\infty,+\infty)\times (-\infty, m] 内所有点的点权和，转化成一个特殊的动态矩形加、矩形和问题。

对于 d 维欧式空间中的在线 d 维矩形加，矩形求和（半群信息），这篇文章给出了一个对任意 T_{\mathrm{qry}}(n),T_{\mathrm{upd}}(n) 满足 T_{\mathrm{qry}}(n)\times T_{\mathrm{upd}}(n) = n，\widetilde{O}(n) 空间，修改耗时 O(T_{\mathrm{upd}}\log^d n)，查询耗时 O(T_{\mathrm{qry}}\log^d n) 的结构。且同样通过 OMv 归约证明了 \widetilde{O}(n^{1.5}) 是目前的复杂度下界。