本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-14 16:08:25

OMv(Online Matrix–Vector multiplication)猜想：

给定布尔矩阵 $M \in \{0,1\}^{n\times n}$，接下来会收到 $n$ 个 $n$ 维布尔向量 $v^{(1)},\dots,v^{(n)}$，在线回答 $$ Mv^{(t)} $$ 的结果，这里将矩阵乘法定义中的 $+$ 换为 $\ee$，$\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})$ 是目前的复杂度下界。