子乘积树

逐个构造 $\prod _j{m}_j$ 会反复把一个越来越大的乘积乘以小因子，无法充分利用快速乘法。子乘积树把大小相近的多项式配对：先做许多一次乘一次，再做二次乘二次，直到根部只剩一次大乘法。这个均衡安排正是分治公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。在乘法成本为超线性时发挥作用的地方。

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

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

第一层两结点是

根则为

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

重复点并不妨碍建树：点列 $(1,1,2)$ 的根仍是 $(x-1{)}^2(x-2)$。但普通 Lagrange 插值要求线性因子两两互素，重复点使 $M^{\prime }(1)=0$，不能直接求倒数；此时需要带导数数据的 Hermite 插值。对一般模数，若它们不互素，批量余式仍有定义，Chinese remainder 重构却不唯一。树结构本身不替下游算法保证互素性。

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

子乘积树向下支撑快速多点求值公理库快速多点求值Fast multipoint evaluation · Multipoint polynomial evaluation沿子乘积树递归取余，在准线性乘法代价上批量计算一般点集的多项式值。：每个结点携带对其叶子乘积的余式。向上则支撑乘积树快速插值公理库乘积树快速多项式插值Product-tree polynomial interpolation · Fast interpolation by product tree以根积导数权重和自底向上线性组合，在一般互异点集上快速恢复插值多项式。：左右局部线性组合分别乘以对侧的子积，再相加成为父结点答案。同一骨架还实现多模约简、多项式 Chinese remainder 重构和批量有理函数求值。

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