算法简介
我们常常遇到一些形如给定 \(n\) 个函数上的点 \(P_i(x_i,y_i)\)，求函数 \(f(x)\) 的值的问题。解决此类问题的重要方法之一便是拉格朗日（Lagrange）插值法。
算法概述
基本型
我们考虑记点 \(P_i(x_i,y_i)\) 在坐标系上的投影为 \(P_i'(x_i,0)\)。那么我们不妨构造 \(n\) 个函数 \(f_1,f_2,\cdots,f_n\) 使得 \(f_i\) 经过：
\[\begin{cases}
P_i(x_i,y_i) \\ P_j(x_j,y_j) & i \ne j
\end{cases}
\]
那么我们最后要求的 \(f(x) = \sum_{i=1}^{n} f_i(x)\)。
不妨设 \(f_i(x) = t \times \Pi_{i\ne j} (x-x_j)\)，代入坐标容易得出 \(t = \frac{y_i}{\Pi_{i\ne j} (x_i-x_j)}\)，那么 \(f(x)=\sum_{i=1}^{n} y_i \times \Pi_{i\ne j} \frac{x-x_j}{x_i-x_j}\)。
直接算时间复杂度就是 \(O(n^2)\)。运用一些技巧可以优化到 \(O(n\log^2 n)\)。
连续横坐标
横坐标连续时，把式子改造一下可以做到 \(O(n)\)。