Linear-time evaluation from a full cube table

Start with the one-entry array $W_0(())=1$. At stage $i$, replace each entry $W_{i-1}(b)$ by entries $W_i(b,0)=W_{i-1}(b)(1-r_i)$ and $W_i(b,1)=W_{i-1}(b)r_i$. After stage $i$ each entry is the product of the appropriate first $i$ factors, directly by this recurrence. This remains valid for zero or unit coordinates.

After stage $n$, return ${\sum }_{b}f(b)W_n(b)$. The weights equal the interpolation basis evaluated at $r$, so this is $\tilde{f}(r)$. Zero tables or zero weights need no separate treatment.

The weight construction costs $O({\sum }_{i=1}^n{2}^i)=O(2^n)$ operations, and the final weighted sum costs $O(2^n)$. Holding the table, two successive weight arrays and $r$ uses $O(2^n+n)$ storage. For $n=0$, return the sole table entry; for $n=1$, the construction returns $(1-r_1)f(0)+r_{1}f(1)$. The input still has $2^n$ values.