O(n^{2-eps}) 3sum

chen_zhe · 2026-10-06 12:57:08 · 算法·理论

给你一个整数数组，判断是否存在三个互异下标，使对应的数加起来等于零。这就是 3SUM。

学过双指针的同学，很快就能写出一个 O(n^2) 的算法：先排序，枚举第一个数，再从剩余区间的两端向中间移动，寻找另外两个数。这个做法简洁、实用，也一直是理解 3SUM 的起点。

论文《Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs》提出了一个指数更小的算法：对绝对值为 n^{O(1)} 的整数，确定性地在 O(n^{1.9992}) 时间内解决 3SUM。

这里的“指数更小”需要认真区分。n^2/\log n 也比 n^2 小，但它节省的是对数因子。这篇论文要做到的是：存在一个固定常数 \varepsilon>0，时间为 O(n^{2-\varepsilon})。虽然这里的 \varepsilon 很小，仍然属于严格的指数改进。

这篇文章沿着整数 3SUM 的主线，解释新算法为何正确、每一笔主要开销如何计算，以及 1.9992 是怎样得到的。读者需要知道数组、图、递归、矩阵乘法的定义和基本复杂度分析。涉及的代数构造会在正文中展开；实数版本及其他应用只在最后说明它们与主线的关系。

一、先找到真正需要优化的任务

先暂时放下数组，考虑一个更形象的问题。左边有 N 个人，右边有 N 个人，中间只有 D 个人。我们知道左边每个人认识哪些中间人，也知道右边每个人认识哪些中间人。现在给出一些指定的左右配对，要求回答：每一对有多少共同认识的中间人？

把“认识”记成 1，“不认识”记成 0。左侧关系形成一个 N\times D 的矩阵 X，右侧关系形成一个 D\times N 的矩阵 Y。左右两个人的共同朋友数，恰好是矩阵乘积的一个条目：

例如，左侧某人的关系是 (1,0,1)，右侧某人的关系是 (0,1,1)，对应内积为 1。它们共同认识第三个中间人。在图论中，共同朋友叫共同邻居；如果再连接这两个端点，就组成一个三角形。

用 W 表示要求计算的位置集合。直接处理一个位置需要 O(D) 时间，所以逐个查询要 O(|W|D)。另一种办法是计算整个矩阵乘积，但完整结果有 N^2 个数，仅写下它们就需要 \Omega(N^2) 时间。

论文利用的限制有两个：矩阵很薄，即 D 相对于 N 很小；要求的输出很稀疏，即 |W|\le N^2/\sqrt D。在 N\ge D^{18} 时，作者希望把指定位置的总计算时间降到 O(N^2/D^\gamma)，其中 \gamma 是一个固定正数。

这个目标没有违背输出规模的下界。要求输出的数量只有 N^2/\sqrt D，而最终使用的 \gamma=0.063 小于 1/2，时间预算仍大于输出数量。困难在于：怎样在不计算整张结果表的情况下，让任意给出的查询也能共享足够多的工作？

下面先建立新矩阵算法，再解释原始 3SUM 如何使用它。主线是：

3SUM
  → 少量卷积 3SUM 实例
  → 许多个较小的带权三角形实例
  → 稀疏的共同邻居查询
  → 薄矩阵乘积的指定位置
  → 共享编码、剪枝与盒子预处理

二、一个小恒等式，为什么能改变大量计算

快速矩阵乘法常用一种策略：把几个计算混在一起，用较少的乘法得到一些中间结果，再用加减法组合出答案。一个很小的恒等式，只要能够反复使用，就可能改变大问题的指数。

这篇论文使用的基础构造来自 Schönhage。先准备三个数 x_1,x_2,x_3 和三个数 y_1,y_2,y_3，要计算九个乘积 x_iy_j。它们是一个三维向量与另一个三维向量的外积，可以看成 3\times1 与 1\times3 的矩阵乘法。

另外准备四个数 p_{11},p_{12},p_{21},p_{22} 和四个数 q_{11},q_{12},q_{21},q_{22}，要计算一个四项内积 H=\sum_{i,j=1}^{2}p_{ij}q_{ij}。单独完成这两组任务，需要 9+4=13 次乘法。

为了让两组任务产生联系，先扩展两个小表：

第一个表的每一列之和为零，第二个表的每一行之和为零。接着计算九个数 T_{ij}=(x_i+\widehat p_{ij})(y_j+\widehat q_{ij})，以及第十个数 T_0=-(x_1+x_2+x_3)(y_1+y_2+y_3)。

把十个数相加，展开后得到：

因此，十次乘法确实精确算出了内部的四项内积。不过，外部输出 T_{ij} 与想要的 x_iy_j 之间还有差值 x_i\widehat q_{ij}+\widehat p_{ij}y_j+\widehat p_{ij}\widehat q_{ij}。

这个差值的结构非常重要：每个多余项至少使用了一个内部输入变量，也就是某个 p 或 q。外部输入只有 x,y 的时候，外积输出就是精确的。

所以这一步得到的是一个带有特殊多余项的计算构造。接下来，作者要安排递归输入，让最终所需输出永远遇不到这些多余项。

为了描述递归，把计算 T_0 的分支叫 P_0，计算 T_{ij} 的分支叫 P_{ij}。P_0 中的 0 只是编号，分支的数值并不一定为零。内部输出使用全部十个分支之和；外部输出 (i,j) 只使用对应分支 P_{ij}。后面能够剪枝，依赖的正是这种简单的输出关系。

三、递归如何同时容纳很多个矩阵乘法

把刚才的构造使用 L 层，可以想成给每个数组下标增加了 L 个位置。每个位置都可以选择内部变量或外部变量。

如果某个小乘法在恰好 m 个位置选择内部计算，这 m 个位置的四种内部下标共同组成一个长度为 D=4^m 的求和下标。其余 L-m 个位置，各提供三种行选择和三种列选择，所以行数和列数都是 N_0=3^{L-m}。这恰好是一个 N_0\times D 与 D\times N_0 的乘法。

例如，只有三层，在中间一层选择内部计算，其余两层选择外部计算，就对应 9\times4 与 4\times9 的矩阵相乘。行号来自前后两个三选一的位置，中间的四选一位置负责对四个乘积求和。

用 Q 表示选择内部计算的层号集合。大小为 m 的 Q 一共有 K=\binom Lm 种。因此，同一个递归布局可以同时容纳 K 个小矩阵乘法，每个乘法拥有不同的内部集合 Q。不同矩阵的元素放在不同字符串下标里。

这里必须验证：把这么多任务装在一起，外部多余项会不会让任务互相干扰？作者的规则是，左右输入只在“内部位置恰好有 m 个”的下标处允许非零，其他位置全部填零。

考虑内部集合为 Q 的某个目标输出。这个输出在 Q 的每一层都要求精确内积。根据上一节的恒等式，能够贡献给内部输出的项，只能同时选取下标匹配的内部输入 p_{ij},q_{ij}。因此，两侧输入在 Q 的全部 m 个位置上都必须是内部变量。

输入总共只允许有 m 个内部位置，所以它们在 Q 之外必须全部为外部变量。外部的每个多余项都要求至少一个内部变量，这时就无法出现。两侧输入的内部集合也只能都是 Q，因此其他小矩阵的数据不会串入这个输出。

每一项非零贡献都属于正确的小矩阵，并且具有相同的求和下标。把这些项相加，就得到普通矩阵乘法的答案。这是整个代数部分最重要的正确性理由。

有了这项批量计算能力，还要把它用于一个更大的 N\times D 与 D\times N 乘法。将 X 每 N_0 行分成一个行块，将 Y 每 N_0 列分成一个列块。一个行块与一个列块的乘积，就是刚才的小乘法。

每次取 K_0=\lfloor\sqrt K\rfloor 个行块和同样多的列块，组成一个方形计算块。它含有 K_0^2\le K 个小乘法，给每个小乘法分配不同的 Q，剩余位置填零。大矩阵最终由这些方形计算块覆盖。

这种方形组织方式还有一个用途：一个计算块的左侧输入只依赖它使用的行带，右侧输入只依赖它使用的列带。下一节将利用这一点共享预处理。

四、先共享准备工作，再剪掉无用分支

递归树每层有十个分支。一个长度为 L 的分支字符串 \tau 对应一片叶子。叶子上的乘法可以写成 \Phi_\tau(X)\Psi_\tau(Y)：第一个因子是对应左输入的一些元素做加减，第二个因子是对应右输入的一些元素做加减。

这些线性组合称为编码。关键是，左编码完全不需要知道右输入，右编码也不需要知道左输入。

同一个行带要与很多列带配对。若每次配对都重新编码，费用会超过预算。现在每个行带的左编码只做一次，每个列带的右编码只做一次，所有使用它们的计算块都读取同一份编码。

一次完整编码需要 O(10^L) 运算，而不是免费。它可以通过递归的加减阶段生成：深度 k 有 10^k 个调用，每个处理大小约为 7^{L-k} 的输入数组，将各层费用求和得到 \sum_kO(10^k7^{L-k})=O(10^L)。

行带和列带数量都是 O(N/(\sqrt K N_0))，所以共享编码的总费用是 O(N10^L/(\sqrt K N_0))。论文选择参数并要求 N\ge D^{18}，确保编码总费用能压进最终预算。它同时确保一个方形计算块能放进大矩阵；不能整除的边界用零补齐，只增加常数倍尺寸。

编码完成后，可以专心处理输出。如果一个输出在某层是外部 (i,j)，只需递归进入 P_{ij}；如果它在某层是内部输出，就要进入全部十个分支。所以，一个内部集合为 Q 的输出，依赖的叶子是：Q 的 m 个位置任意选择十个分支，其余位置固定。

单个输出依赖 10^m=D^{\log_4 10} 片叶子，甚至超过直接内积所需的 D 次乘法。因此，新算法依赖的是多个输出的叶子并集。共享的叶子在同一计算块中只做一次。

实现剪枝时，给每个递归调用传一个“需要哪些输出后缀”的集合 S。外部切片 S_{ij} 与内部切片 S_{\mathrm{in}} 都需要分支 P_{ij}，所以这个分支接收两者的并集；P_0 只接收内部切片。空集合对应的调用直接跳过。可以写成下面的伪代码：

Pruned(prefix, S):
    若 S 为空，返回空结果
    若 prefix 已有 L 个分支：
        读取该叶子的左右编码，相乘后返回

    按首符号，把 S 分成内部切片 S_in 和九个外部切片 S_ij
    child[P_0] = Pruned(prefix + P_0, S_in)
    对每个 (i, j)：
        child[P_ij] = Pruned(prefix + P_ij, S_in ∪ S_ij)

    对 S 中每个外部输出 (i, j) + suffix：
        答案是 child[P_ij][suffix]
    对 S 中每个内部输出 + suffix：
        答案是十个 child 在 suffix 处的值之和
    返回这些答案

只数叶子还不够，集合分发与解码也要收费。作者证明，固定深度时，所有调用所需后缀的总数不超过最终访问的叶子数。方法是将一个调用路径及其后缀补成叶子：后缀的内部符号补 P_0，外部符号补对应 P_{ij}。给定这片叶子及当前深度，可以恢复调用路径和后缀，所以不同记录不会映射到同一叶子。

递归有 L+1 个深度，每条字符串处理长度至多 L。因此，集合处理、查表和解码合计可控制为每片访问叶子 O(L^2)。长度为 L、字母表大小固定的字符串也可以用基数排序或 trie 组织，不需要偷偷支付一个无法控制的排序费用。

五、叶子计数怎样产生一个固定指数

下面进入论文最重要的新观察。对某个输出，把内部位置全部选择 P_0，其余位置选择该输出指定的 P_{ij}，得到一片专属于它的叶子。只在内部位置把若干 P_0 换成九种其他分支，就得到它需要的其他叶子。

定义阶数 d 为替换了多少个内部位置。对于一个输出，d 阶叶子数为 \alpha_d=\binom md9^d：先选替换位置，再选九种分支。

对整个递归树，d 阶叶子恰好含有 m-d 个 P_0，所以总数是 \beta_d=\binom L{m-d}9^{L-m+d}。阶数定义只在能够贡献给目标输出的 0\le d\le m 范围内使用。其他叶子即使存在，也不需要访问。

令 M=K N_0^2=\binom Lm9^{L-m}，表示一个递归布局可容纳的输出数量。阶数零的叶子有 \beta_0=M 片。取 L=19m 后，有：

这里出现了一个值得停下来理解的现象：阶数越大，单个输出需要的这一类叶子越多；但同一叶子也被更多输出共享，整个计算块中这一类叶子的总数反而更少。高阶叶子可以按全局收费，避免给每个输出重复收费。

设一个计算块内要求的输出集合为 U。需要访问的 d 阶叶子不超过 |U|\alpha_d，也不超过全局的 \beta_d，所以取二者较小者。作者在 d=m/9 处切开：低阶部分按指定输出收费，高阶部分按全局数量收费。

低阶部分的关键估计为：

第一步用了 9^d=72^d8^{-d} 和 d\le m/9，第二步是二项式定理。最后只需要核对数值 72(9/8)^9<256。即使 m/9 不是整数，求和只取满足不等式的整数 d，推导仍成立。

高阶部分则是一个等比数列的尾部：\sum_{d>m/9}\beta_d<2M2^{-m/9}。两部分合起来，得到访问叶子数的统一界：

为了直观看到节省，假设一个计算块要求 M/\sqrt D=M/2^m 个输出。低阶部分的费用是 (M/2^m)2^{8m/9}=M/2^{m/9}，高阶部分也是同一个量级。2^{m/9}=(4^m)^{1/18}=D^{1/18}，于是相对于完整输出规模 M，节省了 D^{1/18} 倍。

实际算法不要求查询均匀分布。上面的界对 |U| 是线性的，把全部计算块相加，只使用 \sum|U|=|W|\le N^2/\sqrt D 和总布局容量 O(N^2)，就得到 O(N^2/D^{1/18}) 片访问叶子。

再加上每片叶子的 O(L^2)=O(\log^2D) 解码费用，以及已经预算好的共享编码，得到论文第 2 节的基础结果：指定位置可在 O(N^2\log^2D/D^{1/18}) 时间内算出。

这一版已经足以产生严格的指数改进。低阶计算利用查询少，高阶计算利用全局数量少；共享编码保证准备工作不会吃掉收益。这三项共同组成完整的复杂度论证。

六、把高阶叶子先求和，得到更强的数据结构

前一版知道全部查询后再剪枝。论文进一步问：如果先处理矩阵、查询以后才来，能否也快速回答？做法是将高阶叶子组成规则的组，提前存储每组的总和。

用星号表示某个位置允许选择全部十个分支。例如，字符串 * P21 * 表示第一、第三层任意，中间固定为 P_{21}，一共包含 100 片叶子。组的数值就是这些叶子的编码乘积之和。论文将满足特定规则的这种组称为盒子。

选一个门槛 t。查询时，阶数小于 t 的叶子单独计算；阶数至少为 t 的叶子从盒子总和中读取。

怎样避免盒子重叠或漏掉叶子？对一个高阶叶子，只查看输出的内部位置 Q，从最大层号向最小层号扫描，直到看到第 t 个非 P_0 分支。已经扫描的内部位置保持不变，尚未扫描的内部位置全部改成星号；外部位置始终固定。

例如，Q 有四个位置，叶子在这些位置依次选择 P_{12},P_0,P_{31},P_{22}，取 t=2。从右向左看到 P_{22},P_{31} 后停止，对应盒子为 * * P31 P22。固定的两个非 P_0 分支确保盒子中每片叶子的阶数都至少为二。

反过来，盒子内每片叶子从右向左扫描时，都会在同一个位置遇到第 t 个非 P_0 分支。因此，每片高阶叶子恰好归入一个盒子。这给出了覆盖完整、互不重复的划分。

每个输出恰好需要 \alpha_t 个盒子。可以这样计数：把一个盒子的星号全改成 P_0，得到该输出的一片恰好 t 阶的叶子；从这片叶子能恢复停止位置和原盒子。所以盒子与该输出的 t 阶叶子一一对应。

一个小例子能把整个查询过程说清楚。输出内部位置为第一、第三层，外部位置固定为 P_{21}，共需要 * P21 * 的 100 片叶子。取 t=1，它们可以分成：

查询读取一片叶子和十八个盒子，就覆盖了原来的一百片叶子。要获得真正的收益，还必须证明这些盒子在全局能够便宜地预处理，并由多个输出复用。

抽离具体输出后，盒子有两条规则：P_0 与星号的总数不超过 m-t；所有星号的层号都小于所有 P_0 的层号。非 P_0 的其他位置各有九种选择。

把星号全替换为 P_0，得到一片阶数至少为 t 的叶子。给定这片叶子，要满足层号规则，只能把它最靠前的一段 P_0 改成星号，选择数不超过 m+1。因此全局盒子总数至多为 (m+1)\sum_{d\ge t}\beta_d。

盒子的总和也能动态规划。无星号的盒子就是一片叶子，直接读取左右编码相乘。有星号时，将层号最大的星号依次替换成十种具体分支，得到十个少一个星号的盒子，它们的值之和就是原盒子的值。替换成 P_0 后，它位于其他星号之后，仍满足规则；替换成其他分支也不破坏规则。于是按星号数从少到多计算，状态始终封闭。

用 trie 存储长度为 L 的盒子字符串，每个盒子的生成、十次查表和插入只需 O(L) 时间。高阶叶子的数量界控制了盒子的总数量，这个动态规划又控制了每个盒子的计算费用。

七、为什么最后使用的是 0.063 与 0.437

增强版取 L=21m、t=\lceil m/9\rceil。这时全局叶子的衰减比例满足 \beta_d/\beta_{d-1}\le\rho=9m/(20m+1)<9/20。因此，预处理高阶盒子的数量大致带有 (9/20)^{m/9} 的节省。

把它换算成 D=4^m 的指数，得到 \gamma=\ln(20/9)/(9\ln4)=0.064000\ldots。其中 \ln 表示自然对数。计入生成与查表费用后，盒子预处理为 O(N^2m^2/D^\gamma)。

查询需要读取低于 t 阶的叶子以及 \alpha_t 个盒子，所以读取项目总数是 \sum_{d=0}^{t}\alpha_d。沿用前一节低阶计数的方法，并处理 t 向上取整，得到它不超过常数倍的 72^{m/9}(9/8)^m。对应指数为 q=(\ln72+9\ln(9/8))/(9\ln4)=0.427736\ldots，查询时间为 O(mD^q)。

共享编码必须一起检查。需要证明 N10^L/(\sqrt K N_0) 不超过 N^2/D^\gamma，等价于 D^\gamma10^L/(\sqrt K N_0)\le N。将 L=21m 代入并估计二项式系数，左侧至多为 \sqrt{21m+1}\,\Lambda^m，其中 \Lambda\approx4.1986\times10^{10}。假设给出的基数是 4^{18}\approx6.8719\times10^{10}，比 \Lambda 大，最终能压住前面的多项式因子。将 D 补到 4 的幂只影响常数；论文给出的一个充分阈值是 m\ge60。更小的 m 对应有固定上界的 D，可采用直接计算并增大统一常数。

这里不能把对数因子直接扔掉。不过，可以稍微放宽指数来吸收它们：\gamma>0.063、q<0.437，而 m=O(\log D)。于是最终得到：

对至多 N^2/D^{0.5} 个指定位置，查询总时间是 (N^2/D^{0.5})D^{0.437}=N^2/D^{0.063}，与预处理同阶。0.437 是便于配合查询数量使用的安全上界，实际推导得到的 q 更小。

这里的空间界包括行列编码和盒子表。输入本身的 O(ND) 个数也在预算内：N\ge D^{18} 保证 ND\le N^2/D^{0.063}。

至此，我们有了后续问题需要的工具：对薄矩阵乘积的指定条目，确定性地节省一个 D^{0.063} 因子。

八、带权三角形怎样使用这个工具

现在回到带权三角形。三个点集 A,B,C 各有 s 个点，每条边有整数权值，绝对值不超过 U，统一取 U\ge1。目标是找到满足 S(a,b,c)=w(a,b)+w(a,c)+w(b,c)=0 的三角形。逐个检查要 O(s^3) 时间。

为了把数值条件转换成共同邻居条件，先选一个大小约为 \sqrt D 的素数 p，暂时只检查 S(a,b,c)\equiv0\pmod p。真正的零一定仍然满足模零，但某些非零和也可能是 p 的倍数。把这些错误候选称为假阳性，最后用原始权值检查。

先看模零条件如何变成一个薄矩阵任务。将 (a,b) 按边权 w(a,b) 模 p 的余数 \rho 分组。同一组内的条件可以改写为 w(a,c)+\rho\equiv-w(b,c)\pmod p。

把第三部分切成许多小块，每块约有 \sqrt D/g 个点，其中 g 是可调参数，1\le g\le\sqrt D。对一个小块，建立中间点 (c,\sigma)，其中 \sigma 枚举模 p 的全部余数。左侧点 a 连接满足 \sigma\equiv w(a,c)+\rho 的中间点；右侧点 b 连接满足 \sigma\equiv-w(b,c) 的中间点。

这时，(a,b) 有共同邻居，当且仅当该小块中存在模零三角形。中间点数量约为 (\sqrt D/g)p=O(D/g)，可补齐为至多 D 个点。左右两侧各有 s 个点，因此形状符合薄矩阵算法。

还要保证查询数不超标。每个余数组再切成至多 s^2/\sqrt D 对的查询块。全部余数组合计只需 O(\sqrt D) 个查询块；第三部分小块数是 O(sg/\sqrt D)。将两者配对，共有 O(sg) 个薄矩阵任务，每个任务时间 O(s^2/D^{0.063})。

于是，使用矩阵算法的总费用为 O(s^3g/D^{0.063})。参数 g 越大，小块越短，但任务越多。短块有利于最后扫描精确见证，接下来要计算这部分费用。

选素数与控制假阳性

这一步必须确定性地保证候选不太多。任意非零和的绝对值不超过 3U。如果它被很多个大小约为 \sqrt D 的不同素数整除，这些素数的乘积也整除它，乘积很快就会超过 3U。因此，一个非零三角形只能对少量候选素数产生假阳性。

在 [\sqrt D/2,\sqrt D) 内有数量级为 \sqrt D/\log D 的候选素数。每个非零和能被这一范围中至多 O((1+\log U)/\log D) 个素数整除。将全部非零三角形对全部候选素数的贡献相加，再取平均，分子、分母中的 \log D 抵消，得到至少一个素数满足：

其中 F(p) 为假阳性三角形总数。

如何找到这个素数？计算每个候选素数下的模零三角形总数，选择总数最少的一个。设真正零三角形数为 Z_0，这个计数等于 Z_0+F(p)。Z_0 对所有素数相同，所以最小化总计数就等于最小化假阳性数，无需事先知道真正答案。

计数也要有快速算法。把一条边的余数 r 记录为单项式 z^r；相乘时指数相加；再规定指数每到 p 就绕回零，即按模 p 处理。两个这样的多项式相乘，就是长度 p 的循环卷积，其某个系数记录了相应余数出现多少次。

将两侧边记录为多项式矩阵，做一次矩阵乘法，再读取每对 (a,b) 所需余数的系数，就得到模零三角形总数。Strassen 算法可以在这套加乘规则下使用；每次多项式乘法采用直接 O(p^2) 方法已足够。全部候选素数的总费用为 O(s^{\log_2 7}D^{3/2})。

矩阵查询接受某对端点后，扫描对应的第三部分小块，用原始权值检查 S=0。若存在真正答案，它所在小块的查询一定接受，扫描也一定找到它。若一次扫描失败，这个小块中至少有一个模零但非零的三角形。不同端点与不同小块对应不同三角形，所以不同失败扫描可以对应到不同假阳性。

失败扫描次数至多 F(p)，每次扫描约 \sqrt D/g 个点。总扫描费用为 O(s^3(1+\log U)/g)；成功扫描最多发生一次，因为找到答案就结束。

平衡费用，得到次三次的三角形算法

省略对数因子后，主要开销是 s^3g/D^{0.063}+s^3/g。为了同时压低两项，令 g=D^{0.0315}。两项都变成 s^3/D^{0.0315}。

薄矩阵算法还要求 s\ge D^{18}，所以把厚度取到允许的上限 D\approx s^{1/18}。指数因此变为：

其余费用没有超过主项。选择素数的费用为 s^{\log_2 7+1/12}，指数约 2.891<2.9；生成所有图任务的费用为 O(s^2Dg)，指数约 2.0573。向上、向下取整只影响常数，小规模实例用暴力处理。

如果 U 是规模的多项式，1+\log U=O(\log s)，于是得到 O(s^{2.99825}\log s)。保留独立参数 U 更严谨：归约中的小子实例可能仍携带原问题的大权值，统一界 O(s^{2.99825}(1+\log U)) 可以继续使用。整数存储采用原问题的 O(\log n) 位字长，容纳这些权值所需的常数个字。

这里也说明了第一个指数损失：矩阵节省的 D^{0.063}，有一半用来降低任务数量与扫描成本之间的冲突，留下 D^{0.0315}；厚度限制再把它换成 s^{0.00175}。

九、3SUM 如何变成卷积 3SUM

前面得到了快速三角形算法。现在解释 3SUM 的输入如何送到它手里。这一部分主要沿用论文引用的已有确定性归约，下面用适合数组学习者的形式展开其机制。具体参数的对数因子不影响最终固定指数。

首先处理三个下标必须互异的问题。把输入下标写成二进制。对任意三个不同下标，总有某一位把一个下标与另外两个分开；再有另一位把后两个分开。

枚举这两位及第一位的方向，把满足第一位某值的下标放入第一组，第一位为另一值且第二位为零的放入第二组，第一位为另一值且第二位为一的放入第三组。三个组互不相交，枚举数为 O(\log^2n)。将第三组元素取相反数，问题成为从三个组中各选一个值，满足 a+b=c。每个原始解至少出现在某个分组实例里，每个分组实例的解也保证下标互异。

每个组内部可以按值去重，因为只需从该组选择一个元素；跨组相同的值仍允许分别选择。接下来，三个组都是由不同整数构成的集合，数值绝对值不超过 U=n^{O(1)}。

卷积 3SUM 的形式是：给定三个数组 u,v,w，寻找下标 i,j，使 u[i]+v[j]=w[i+j]。它多了一个限制：数值必须相等，存放数值的下标也必须满足加法关系。直接按输入顺序放置元素无法保证这个关系，所以要让下标由数值的余数决定。

设模数为 h。将元素 a 放到数组下标 a\bmod h。如果某个桶中只有一个值，就能唯一确定该位置该存什么。对于 a+b=c，余数下标满足 (a\bmod h)+(b\bmod h)=(c\bmod h) 或 (c\bmod h)+h。把第三组的数组复制两遍，就能吸收这一位进位。

例如，模数为五，a=7,b=9,c=16。三者的余数为二、四、一；前两个下标相加为六，所以第三数组既在下标一存十六，也在下标六存十六。卷积查询因此可以发现 7+9=16。

桶碰撞是剩下的问题。如果同一组多个元素被放到一个下标，只存一个可能丢解。做法是先处理每组的单元素桶，再递归处理发生碰撞的元素。想保持高效，就需要一个能把碰撞压得很小的模数。

两次选素数，为什么能压低碰撞

这一段可以把两次选择理解为：先缩小可能碰撞的元素对，再从这些元素对里筛一遍。下面给出确定性保证，不需要随机选择素数。

在当前递归节点，三个集合大小分别为 r_1,r_2,r_3，都不超过原始规模 n。空集合直接返回无解。对于模数 h，记 C_i(h) 为第 i 组中“不同值但余数相同”的有序元素对数量。用分数 E(h)=\sum_i C_i(h)/r_i^2 衡量碰撞情况，较小的组也会被公平地考虑。

取一个候选素数集合，共有 P 个素数。一个非零差值的绝对值不超过 2U，最多被 \lambda=\lceil\log_2(2U)\rceil+1 个不同素数整除，因为不同素数的乘积至少按二的幂增长。对全部候选素数平均，至少一个素数 p 满足 E(p)\le3\lambda/P。逐个计算碰撞分数，选最小者即可确定性找到这样的 p。

接着仍从候选集合里选一个素数 q，把模数改成 pq。只有第一轮已经模 p 碰撞的元素对可能留下。对于这一对，pq 整除差值，等价于 q 整除非零整数“差值除以 p”。后者仍只有至多 \lambda 个候选素因子。因此再取一次平均，能选到 q 满足：

两个素数不必不同；即使 q=p，第二轮检查的也是差值能否再除以一个 p。

选择足够多的候选素数，使 P\ge\sqrt{6n}\,\lambda，就得到 E(pq)\le1/(2n)。可以让全部候选素数不超过 R=\sqrt n\,(\log(nU))^{O(1)}，因此最终模数 h=pq\le R^2=n(\log(nU))^{O(1)}，卷积数组长度仍接近 n。

这一保证同时控制每个组：C_i(h)\le r_i^2/(2n)。桶中若有 k\ge2 个元素，会产生 k(k-1)\ge k 个有序碰撞对，所以该组所有碰撞桶里的元素数量也至多 r_i^2/(2n)。

设某组当前有 r=n/k 个元素，递归到它的碰撞部分时，剩余数量至多 n/(2k^2)。规模每次变化满足 k\mapsto2k^2，缩小速度比简单减半更快。

递归怎样覆盖所有解，又不产生太多任务

当前节点先用每组的单元素桶生成一个卷积实例。若一个原始解的三个元素都在单元素桶内，它会被这个实例发现。若至少一个元素在碰撞桶中，就进入三个递归分支中的至少一个：分别把第一、第二、第三组替换成自己的碰撞部分，另外两组保留当前全集。

这个覆盖可能让一个解出现在多个分支里，但我们只判断是否存在，所以重复不会影响正确性。任何分支中的元素仍来自原来的三个组，因而不会产生不合法的原始解。

沿递归路径，每次至少有一个组满足上述平方速度的缩小。对一个组，经过 O(\log\log n) 次这样的缩小就会变空。三个组共使路径深度为 O(\log\log n)；每个节点只有三个分支，所以节点数为 3^{O(\log\log n)}=(\log n)^{O(1)}。

确定性选择素数的开销也符合预算。对每个候选，计算元素余数、排序并统计相同余数的桶，在 O(n\log n) 时间内完成；候选数至多 R，两轮共需 n^{3/2}(\log(nU))^{O(1)} 时间。加权分数可以通过整数交叉相乘比较，所有分母均为至多三个 r_i^2 的乘积，仍只有 O(\log n) 位，不依赖实数运算。

最后补上数组空位。两个加数数组的空位填 3U+1，结果数组的空位填 -3U-1；实际元素都在 [-U,U]。任意使用空位的等式都会因数值范围而失败，所以不会产生额外解。前两个数组扩展到长度 2h，在下标 h 以后也填空位值；第三个数组在两段长度 h 中重复存放无碰撞元素。

综合互异下标分组、双素数选择和碰撞递归，3SUM 被转成 n^{o(1)} 个长度为 n^{1+o(1)} 的卷积 3SUM 实例，额外时间为 n^{3/2+o(1)}。这里 o(1) 表示随 n 增大趋向零的量；本段的多项式对数因子都可以写成 n^{o(1)}。

十、把卷积下标拆成高低位，出现平方根规模

现在只需处理一个长度为 q 的卷积实例。令 b=\lceil\sqrt q\rceil，把下标按基数 b 拆成高低位：i=hb+r、j=kb+d，其中 0\le r,d<b。

固定和的低位 \ell\in[0,b)，以及低位相加的进位 e\in\{0,1\}。下标关系变成 r+d=\ell+eb，因此 d=\ell+eb-r；和的高位则是 h+k+e。

固定 (\ell,e) 后，建立三个点集，顶点分别由 h,r,k 标记，每组至多 b 个点。用 \mathrm{cost} 表示图边权，三类边权定义为：

这里 w[\cdot] 始终表示原来的结果数组。任何越界的数组下标，或不满足 0\le\ell+eb-r<b 的边，都不加入图。

一个三角形 (h,r,k) 的权值和为零，恰好表示 u[i]+v[j]=w[i+j]。第一条边读取第一个加数，第二条边读取第二个加数，第三条边读取它们下标和的位置，并取负数。

例如，数组长度为十，取 b=4，考虑 i=6=1\times4+2、j=3=0\times4+3。低位相加为五，所以 \ell=1,e=1；和下标为 (1+0+1)\times4+1=9。图中三角形的边权恰好是 u[6],v[3],-w[9]。它的和为零，当且仅当原等式成立。

任何合法的 (i,j) 都有唯一的低位和进位，所以枚举全部 (\ell,e) 会覆盖全部解。共有 2b=O(\sqrt q) 个图，每个图每部分有 O(\sqrt q) 个点。每张图的边数为 O(q)，构造全部图只需 O(q^{3/2}) 时间。

图不完整时，可以把缺边赋予正整数 3U+1。在这一构造中，任何图边的负值都不小于 -U；数组空位对应的图边也是正的 3U+1。因此，一个含哨兵边的三角形，其权值和至少为 3U+1-2U>0，不可能成为答案。所有权值仍是原输入规模的多项式，可以使用前面的整数三角形算法。

这一节展示了平方根规模的具体来源：一个下标拆成两个约 \sqrt q 范围的数，固定和的低位与进位后，剩下三个自由变量刚好成为三角形的三个顶点。

十一、将指数逐项代回去

为了避免混淆，再列清楚三个规模。n 是原始 3SUM 元素数量；s 是一个带权三角形实例每部分的点数；D 是该实例转换出的薄矩阵厚度。矩阵外部尺寸在这一归约中就是 N=s。

增强矩阵算法节省 D^{0.063}。三角形归约平衡任务数与扫描成本，剩下 D^{0.0315}。厚度至多为 s^{1/18}，所以三角形时间为 s^{3-0.00175} 乘对数因子。

前两段 3SUM 归约合起来，产生至多 n^{1/2+o(1)} 个三角形实例，每个实例规模至多 n^{1/2+o(1)}。有些模数较小，对应图也较小，但权值仍按原始规模 n 有界。这里使用第八节保留全局权值上界 U 的统一时间界；无论实际局部规模多小，1+\log U=O(\log n)，都可以在原问题的字长内处理，再用规模上界统一估计费用。额外时间 n^{3/2+o(1)} 比下面的主项小：

最后一个不等式来自 1.9992-1.999125=0.000075 的正余量。随规模增长，o(1) 最终小于这项余量；不能在没有余量时，直接把 n^{a+o(1)} 写成 O(n^a)。

整个指数传递可以对照下表：

如果只使用第 2 节基础矩阵算法，节省为 D^{1/18}，同样经过两次折半和一次除以十八，可得 3SUM 时间 n^{2-1/1296+o(1)}。这说明基础版已经跨过二次指数，盒子数据结构负责将数值进一步改进。

十二、算法落地时应当对应哪些步骤

从实现角度，完整整数 3SUM 主线的顺序是：先枚举互异下标分组，运行确定性哈希和碰撞递归，生成卷积实例；再枚举低位与进位，生成较小的带权三角形图；每张图选择控制假阳性的素数，生成稀疏共同邻居任务；每个任务调用薄矩阵算法，最后对接受的端点扫描精确见证。

矩阵基础版的实现对应于前面的 Pruned：建立分块和字符串布局，独立计算各行带、列带编码，将指定位置映射为输出字符串，再递归处理非空后缀集合。增强版保留同样布局和编码，另外按星号数动态规划盒子；一个查询只累加低阶叶子和对应高阶盒子。

两层数值安全需要分别注意。矩阵算法中，L=O(\log N)，编码是至多多项式个输入数的有符号和，盒子是至多多项式个编码乘积的和，中间结果仍为 N^{O(1)}，占 O(\log N) 位。归约中，权值、模数、统计数量、字符串编号和交叉相乘后的比较值，也均为原始规模 n 的多项式。因此，在足够常数倍的 \log n 位字长下，每次整数操作占常数时间。

边界可以在进入主算法前统一处理。3SUM 少于三个元素时直接返回无解，重复值由互异下标分组保证合法性；某个三组实例出现空组时直接返回无解。薄矩阵厚度为一时，每个查询只做一次乘法，无需使用递归参数。负数的余数统一取 [0,h) 范围；卷积越界边不加入图；所有用于遮蔽空位或缺边的值，都要按当前数值上界生成，而不是写死一个常数。

论文的矩阵数据结构给出了明确时间和空间界：预处理均为 O(N^2/D^{0.063})，单次查询为 O(D^{0.437})。完整 3SUM 的时间为 O(n^{1.9992})；本文不额外宣称一个没有逐项证明的完整 3SUM 空间指数。

本文用伪代码和明确的数学布局说明新算法。要写出完整工程，需要实现各层编码、盒子生成、确定性哈希和图归约。普通双指针程序依然是 O(n^2)，不能作为这里指数改进的参考实现。这里没有为论文虚构一份竞赛输入格式或通过记录。

十三、最短路、理论意义与阅读范围

论文标题还包含所有点对最短路 APSP。它与矩阵工具的连接，也经过带权三角形，但使用的是另一组已有归约。

最短路常见的转移是“枚举中间点，取两段距离之和的最小值”，对应 (\min,+) 矩阵乘法 C[i,j]=\min_k(A[i,k]+B[k,j])。已有归约能用规模约为 n^{1/3} 的带权三角形求解器，在约 n^2 次调用及对数因子的成本下完成这种乘法。于是三角形的指数节省 0.00175，在这里变成 0.00175/3：

其中 \widetilde O 隐去多项式对数因子。再通过距离矩阵的倍增，得到整数 APSP 的相同固定指数改进。该归约的完整最短路证明属于论文引用的另一条主线；本文展开的是整数 3SUM 及共同使用的矩阵、三角形核心。实数输入还需要比较计数与随机归约，不能直接套用本文的取模步骤。

实际运行方面，隐藏常数很大。编码预算的一项充分阈值使用 m\ge60，对应的 D=4^m 已是极大数值；较小 m 的直接处理合法地并入渐近常数。这个证明阈值不是精确的实用交叉点，却足以说明不能仅凭 1.9992<2 就期待它在日常规模上击败双指针。

理论价值来自一个固定正数的指数节省。对任意固定 C 和 \varepsilon>0，随规模充分增大，n^\varepsilon 最终超过 (\log n)^C。论文提供了一种同时利用稀疏输出、代数计算共享和极端矩形形状的方法，这种方法经已有归约传递到多个问题。

本文的推导对应论文 v1 的整数核心结论。对关键恒等式、误差消除、叶子计数及参数已经进行了人工推导与小规模核查；本文额外将卷积到三角形的构造做了 700 组随机测试，比较全部解的下标对，均一致。有限测试用于发现实现或下标错误，一般性正确性与复杂度仍由上述论证承担。这里没有声称取得评测平台的 Accepted，也没有声称独立编译通过整个 Lean 工程。

参考与原文定位

• Josh Alman、Virginia Vassilevska Williams，Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs，arXiv:2610.06783。本文依据 v1。
• Schönhage 恒等式与误差消除：原文第 16–22 页，Lemmas 6–9。基础剪枝与叶子计数：第 24–29 页，Lemmas 10–11、Theorem 5。
• 高阶盒子、数据结构及参数：第 40–49 页，Lemmas 27–29、Theorem 30、Corollary 26。
• 确定性带权三角形归约与指数代入：第 33–36 页，Theorems 17、19、21、22。
• Timothy M. Chan、Qizheng He，Reducing 3SUM to convolution-3SUM，SOSA 2020。第九节沿该确定性归约的机制给出教学说明，使用加权碰撞计数、单元素桶和下标分组等便于统一分析的表述，未优化对数因子。
• Virginia Vassilevska Williams、Ryan Williams，Finding, minimizing, and counting weighted subgraphs，SIAM Journal on Computing，2013。第十节展开了卷积下标与三角形之间的构造。
• Virginia Vassilevska Williams、R. Ryan Williams，Subcubic equivalences between path, matrix, and triangle problems，Journal of the ACM，2018。

作者公开的形式化工程在 anthropics/formal-math 的 3sum-apsp 目录。核对形式化证据时，应分别检查最终定理的语义、机器模型、证明依赖和实际构建结果；仓库存在与独立复验完成是不同的证据。