Multipoint Evaluation and Interpolation

Evaluate a degree-$n$ polynomial at $n$ arbitrary points in $O(n{\log }^{2}n)$, instead of $O(n^2)$ by repeated Horner.

The idea: a product tree

Build a divide-and-conquer tree over the evaluation points, where each node stores the product $\prod (x-x_i)$ over its range.

                (x-x0)(x-x1)(x-x2)(x-x3)
                /                      \
       (x-x0)(x-x1)              (x-x2)(x-x3)
        /       \                 /        \
    (x-x0)   (x-x1)           (x-x2)    (x-x3)

Building it is $O(n{\log }^{2}n)$ — $\log n$ levels, each doing $O(n\log n)$ of NTT multiplication.

Evaluation — descend with remainders

By the remainder theorem, $P(x_i)=P\mathrm{mod}(x-x_i)$. So descend the tree, replacing $P$ by $P\mathrm{mod}(\text{node’s product})$ at each step. The remainder’s degree shrinks with the node’s range, so the total work per level is $O(n\log n)$.

void evalRec(const Poly& P, int node, int lo, int hi, vector<long long>& out) {
    if (hi - lo == 1) { out[lo] = P.empty() ? 0 : P[0]; return; }
    int mid = (lo + hi) / 2;
    evalRec(P % tree[2*node],   2*node,   lo, mid, out);
    evalRec(P % tree[2*node+1], 2*node+1, mid, hi, out);
}

$O(n{\log }^{2}n)$ overall — the extra $\log$ comes from the polynomial division at each node.

Interpolation — the reverse

Given $(x_i,y_i)$, recover the polynomial. By Lagrange,

$P(x)={\sum }_i\frac{y_i}{M^{\prime }(x_i)}{\prod }_{j\ne i}(x-x_j),M(x)={\prod }_i(x-x_i).$

1. Build the product tree and $M$.
2. Compute $M^{\prime }$ and evaluate it at all $x_i$ by multipoint evaluation — this gives all the denominators at once.
3. Combine bottom-up: at each node, $\mathrm{res}={\mathrm{res}}_L\cdot M_R+{\mathrm{res}}_R\cdot M_L$.

$O(n{\log }^{2}n)$.

The cost table

Task	Naive	Fast
Evaluate at 1 point	$O(n)$	—
Evaluate at $n$ consecutive points	$O(n^2)$	$O(n\log n)$ (a convolution)
Evaluate at $n$ points in geometric progression	$O(n^2)$	$O(n\log n)$ (chirp-z)
Evaluate at $n$ arbitrary points	$O(n^2)$	$O(n{\log }^{2}n)$
Interpolate from $n$ arbitrary points	$O(n^2)$	$O(n{\log }^{2}n)$
Interpolate from consecutive points	$O(n^2)$	$O(n)$ (Lagrange)

Check the point structure first

The special cases are dramatically cheaper. Consecutive points give $O(n)$ interpolation and $O(n\log n)$ evaluation; geometric points give $O(n\log n)$ via the chirp-z transform. Only genuinely arbitrary points need the $O(n{\log }^{2}n)$ machinery — and in contests the points are usually $0,1,2,\dots$

What it enables

Application	Use
Convert between coefficient and value representations	both directions
Fast polynomial GCD (half-GCD)	uses the same product-tree recursion
Polynomial factorisation	evaluating at many points
Chinese remaindering of polynomials	the same tree
$n! \bmod p$ in $\tilde O(\sqrt p)$	evaluate a product polynomial at $\sqrt{p}$ points
Shift a polynomial’s argument	via evaluation and interpolation
Multi-modular CRT reconstruction	the integer analogue of the same tree

$n!\mathrm{mod}p$ in $O(\sqrt{p}{\log }^{2}p)$

Define $f(x)=(x+1)(x+2)\cdots (x+v)$ with $v=\lfloor \sqrt{n}\rfloor$. Then

$n!={\prod }_{i=0}^{v-1}f(iv)\times {\prod }_{j=v^2+1}^{n}j,$

and the $v$ values $f(0),f(v),f(2v),\dots$ are a multipoint evaluation at points in arithmetic progression. Total $\tilde{O}(\sqrt{n})$ — the standard way to compute a factorial modulo a prime when $n$ is around $10^{12}$.

The product tree pattern

Building a balanced tree of products, then descending with remainders, is a reusable structure. The same shape appears in:

• CRT reconstruction from many moduli in $O(n{\log }^{2}n)$;
• fast polynomial GCD (half-GCD);
• batch modular inverse (a linear special case);
• segment trees storing products.

When it is worth it

The constant factor is significant — several NTTs per node. For $n\le 5000$, the $O(n^2)$ Horner loop is faster in practice. Multipoint evaluation earns its place at $n\ge 10^5$, which is rare but real.

See also: Lagrange Interpolation · FFT and NTT · Polynomial Arithmetic