拉格朗日插值法
引入
拉格朗日插值法是一种解决多项式插值的方法。
多项式插值：
已知 \(n + 1\) 个点 \((x_i, y_i)\)， 求一个多项式函数 \(f(x)\) 使得其图像经过这 \(n + 1\) 个点。
其中 \(f(x)\) 被称为插值多项式。
可以证明 \(n + 1\) 个点可以唯一确定一个最高 \(n\) 次的插值多项式。
结论
\[f(k) = \sum\limits_{i = 0}^n y_i \prod\limits_{j \neq i} \dfrac{k - x_j}{x_i - x_j}
\]
可以发现对于一个点 \((x_a, y_a)\)，当 \(i \neq a\) 时，\(\prod\) 部分会有一个 \(\dfrac{x_a - x_a}{x_i - x_a}\)，此时该式子值为 \(0\)。而当 \(i = a\) 时，\(\prod\) 部分的值为 \(1\)。故 \(f(x_a) = y_a\)。
求某一点的值的复杂度为 \(O(n^2)\)。
取值连续时的优化
当 \(x\) 的取值连续，即 \(x_i = i\) 时，可以将复杂度优化到 \(O(n)\)。
\[\begin{align*}
f(k) &= \sum\limits_{i = 0}^n y_i \prod\limits_{j \neq i} \dfrac{k - x_j}{x_i - x_j} \\
&= \sum\limits_{i = 0}^n y_i \prod\limits_{j \neq i} \dfrac{k - j}{i - j}
\end{align*}
\]
令 \(pre_i = \prod\limits_{j = 0}^i (k - j), suf_i = \prod\limits_{j = i}^n (k - j)\)。
则
\[f(k) = \sum\limits_{i = 0}^n y_i \dfrac{pre_{i - 1} \times suf_{i + 1}}{i! \times (n - i)!} \times (-1)^{n - i}
\]
重心拉格朗日插值法
一种可以 \(O(n)\) 插入一个点，\(O(n)\) 查询的拉格朗日插值法。
依然考虑这个式子：
\[\begin{align*}
f(k) &= \sum\limits_{i = 0}^n y_i \prod\limits_{i \neq j} \dfrac{k - x_j}{x_i - x_j} \\
&= \sum\limits_{i = 0}^n y_i \dfrac{\prod\limits_{j \neq i} k - x_j}{\prod\limits_{j \neq i} x_i - x_j} \\
&= \sum\limits_{i = 0}^n \dfrac{y_i}{k - x_i} \dfrac{\prod\limits_{j = 0}^n k - x_j}{\prod\limits_{j \neq i} x_i - x_j} \\
\end{align*}
\]
设 \(g(k) = \prod\limits_{i = 0}^n k - x_i, t_i = \dfrac{y_i}{\prod\limits_{j \neq i} x_i - x_j}\)。
则
\[\begin{align*}
f(k) &= \sum\limits_{i = 0}^n \dfrac{g(k)t_i}{k - x_i} \\
&= g(k) \sum\limits_{i = 0}^n \dfrac{t_i}{k - x_i}
\end{align*}
\]
于是每次插入只需要更新之前的所有 \(t_i\) 并计算当前点的 \(t_i\) 即可，时间复杂度为 \(O(n)\)。
由于 \(g(k)\) 和 \(\sum\limits_{i = 0}^k \dfrac{t_i}{k - x_i}\) 都可以 \(O(n)\) 求得，故询问复杂度也是 \(O(n)\)。