乘积树快速多项式插值

朴素 Lagrange 公式为每个 $i$ 单独构造 $n-1$ 个线性因子的乘积，重复了大量工作。乘积树已经保存所有点集区块的乘积；叶子 $i$ 需要“除掉自己的那一个因子”，向上合并时只要把左侧答案乘右侧整块、右侧答案乘左侧整块，就能一次补齐对方所有因子。每个层级的总次数受控，因而可使用快速乘法。

分母 $M^{\prime }(u_i)$ 不是装饰性的归一化。$M(x)/(x-u_i)$ 在点 $u_i$ 的值恰为 $M^{\prime }(u_i)$，在其他点则因含对应线性因子而为零；除以它以后才得到在 $u_i$ 取 $1$、在其他输入点取 $0$ 的基函数。算法把“基函数的全局性质”拆成叶子权重与树上乘积两部分，各自只算一次。

在有理数域上取点值

根积为 $M=x(x-1)(x-2)=x^3-3x^2+2x$，所以

叶子权重为 $1/2,-2,5/2$。代入合并式，

复算可得 $f(0)=1,f(1)=2,f(2)=5$。这个例子同时显示中间权重可出现分数，即使输入点值全是整数；若目标只是整数系数，算法仍需在某个允许这些除法的域中工作，或采用分母控制版本。

“点两两不同”在一般环上应加强为每个差 $u_i-u_j$ 都是单位。比如在 $\mathbb{Z}/6\mathbb{Z}$ 中，点 $0$ 与 $2$ 虽不同，差 $2$ 不可逆，$M^{\prime }(0)$ 也未必可除，插值可能不唯一或无解。重复点需要给出导数等 Hermite 数据，不能把零分母交给异常处理后继续。

浮点数上还有稳定性边界。显式权重可能极大，树状精确运算的复杂度优势不自动带来良好条件数；数值插值通常选择 Chebyshev 点、barycentric 公式或正交基。这里的结论针对域上的精确算术，若改用近似数，误差分析必须与代数运算数分开。

同一向上合并其实计算了线性映射“点值向量到系数向量”。推广到域上两两互素的首一模数 $m_i$ 时，先记 $M=\prod _i{m}_i$、$B_i=M/m_i$，为目标余数 $r_i$ 计算权重 $c_i=r_i(B_i^{-1}mod{m}_i)mod{m}_i$，再用相同树合并得到 $\sum _i{c}_i{B}_i$。因为第 $i$ 项模 $m_i$ 为 $r_i$、其余项为零，输出满足全部余数且次数小于 $\mathrm{deg}M$。逆因子不可省略；直接把 $r_i$ 当作权重通常不能恢复输入余数。这就是多项式 Chinese remainder 重构；将其与向下的多模约简配对，可在多个商环之间快速转换。批量 rational interpolation、Reed–Solomon 编解码中的某些子程序以及符号求和也会复用这一结构。

若点集固定而 $y_i$ 多次变化，子积树与 $M^{\prime }(u_i{)}^{-1}$ 可以预处理，之后每个新向量只做向上组合。反之，若只有一次很小的插值，Newton 差商的 $O(n^2)$ 简单实现可能更快。算法选择应同时说明点集是否复用、乘法阈值和内存预算；只比较渐近指数会遗漏预处理带来的真实取舍。