子乘积树 | Codeboy's Blog

形式陈述

在交换含幺环 $R$ 上，给定 $n\ge1$ 个用稠密系数保存的多项式因子 $m_0,\ldots,m_{n-1}\in R[x]$ ，先假设 $n=2^h$ 。子乘积树在第 $0$ 层放置

M_{0,j}=m_j,

并递推

M_{i,j}=M_{i-1,2j}M_{i-1,2j+1}, \qquad 0<i\le h.

根为 $M_{h,0}=\prod_jm_j$ 。多点求值采用线性叶子 $m_j=x-u_j$ ，更一般的批量模约简使用非零首一模数；建乘积树本身也允许常数、零多项式以及含零因子的系数环。

令 $\ell_j$ 为第 $j$ 个输入的系数记录长度，并为零多项式至少计一个记录，记 $L=\sum_j\ell_j\ge n$ 。以满足单调、超可加及倍增界的 $M(k)$ 表示长度至多 $k$ 的多项式乘法上界。任一层的各结点对应互不相交的叶子组，某组乘积的系数长度至多该组输入长度之和；系数抵消只会减小它。因此一层的乘法总成本为 $O(M(L))$ 。连同读入与保存，完整建树成本为 $O(M(L)\log(n+1))$ 。线性叶子时 $L=2n$ ，该式化为 $O(M(n)\log(n+1))$ 。

该对象是带多项式标签的平衡二叉树，而不是只保存叶子乘积的一个公式。保留全部层时，每层系数记录和结点数均为 $O(L)$ ，总空间为 $O(L\log(n+1))$ ；若某次算法只需相邻两层，可以用重算或流式释放降低峰值空间。非二次幂叶子数可以建不完全平衡树，也可补单位多项式 $1$ ；补 $1$ 不改变根积，却不能把它误当成额外求值点。

直觉

逐个构造 $\prod_jm_j$ 会反复把一个越来越大的乘积乘以小因子，无法充分利用快速乘法。在线性叶子的情形，子乘积树把次数相近的多项式配对：先做许多一次乘一次，再做二次乘二次，直到根部只剩一次大乘法。一般叶子的次数可以不同；按叶子数平衡仍保证树高，逐层的总系数预算给出上面的成本界。这个均衡安排正是分治在乘法成本为超线性时发挥作用的地方。

更重要的是，中间结点记录了叶子集合的“共同模数”。从根向下计算余式时，父结点上的一个余式只需分别模两个子结点，而无需重新处理原始大多项式；从叶子向上插值时，兄弟结点的乘积又提供了把两块局部答案嵌回全局的乘子。因此树的价值不只是更快得到根积，而是保存了一张可沿两个方向遍历的代数路由图。

例子与边界

对求值点 $1,2,4,5$ ，四个叶子为

x-1,\quad x-2,\quad x-4,\quad x-5.

第一层两结点是

M_{1,0}=x^2-3x+2,\qquad M_{1,1}=x^2-9x+20,

根则为

M_{2,0}=x^4-12x^3+49x^2-78x+40.

若随后要把多项式 $f$ 模每个 $x-u_j$ ，先算 $f\bmod M_{1,0}$ 与 $f\bmod M_{1,1}$ ，再各自向两个叶子下降即可。同一棵树可供多个 $f$ 复用，所以“预处理点集”和“处理一次查询”的成本必须分开报告。

重复点并不妨碍建树：点列 $(1,1,2)$ 的根仍是 $(x-1)^2(x-2)$ 。但普通 Lagrange 插值要求线性因子两两互素，重复点使 $M'(1)=0$ ，不能直接求倒数；此时需要带导数数据的 Hermite 插值。对一般非零首一模数，批量余式仍有定义；Chinese remainder 的唯一重构还要求各模理想两两互素。不满足时，指定余数可能不兼容，即使兼容也可能在模根积意义下不唯一。例如两个叶子都为 $x$ 、余数都为零， $0$ 与 $x$ 就是模 $x^2$ 不同的两个解。树结构本身不替下游算法保证互素性。

复杂度式还隐藏了存储边界。保留全部层虽然渐近上方便，却可能让大系数复制占主导；只保存根又会迫使每次下降重新建子积。最佳策略取决于查询次数和内存预算。对于单位根等特殊点集，FFT 可直接一次变换求值，通用子乘积树的额外 $\log n$ 层未必值得。

推论与应用

子乘积树向下支撑快速多点求值：每个结点携带对其叶子乘积的余式。向上则支撑乘积树快速插值：左右局部线性组合分别乘以对侧的子积，再相加成为父结点答案。同一骨架还实现多模约简、多项式 Chinese remainder 重构和批量有理函数求值。

在复杂算法中，树常与反转多项式的快速除法结合。模数都是首一时，长除法不需要倒置不可逆的首项；若使用 Newton 反演加速，还要确保相应反转多项式的常数项为单位。把这些代数条件写在余式子程序接口中，可以让上层树递归只负责划分点集，不把“某次除法是否存在”分散到每个结点。

参考资料

Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013, Ch. 10.
Robert T. Moenck and Allan Borodin, “Fast Modular Transforms,” Journal of Computer and System Sciences 8(3), 1974, pp. 366–386.
Arne Storjohann, CS 487/687 Symbolic Computation: Script 7—Fast Evaluation and Interpolation, University of Waterloo lecture notes.

形式陈述 ​

反向链接

形式陈述