Based on a previous question which turned out at least in it's exact form to have a rather complicated and unfulfilling answer... If we want to approximate a polynomial sum at integer positions: $$\sum_{k=0}^NP(k)$$
Undergrad education ghost would whisper to me there exists some polynomial $Q$ so that $$\int_{0}^{N+\xi} Q(t)dt = \sum_{k=0}^{N}P(k)$$
Firstly, is it true? Would $\xi$ be easy to determine? Or would it just be a useless curiosity?
This is actually easier than seems. And we can show that we can choose $\xi = 0$, and replace $Q$ above with $q$ so that $q$:s primitive is called $Q$ instead:
$$P(k+1) = \int_k^{k+1} q(t)dt = \left[Q(t)\phantom{\frac{}{}}\right]_{k}^{k+1} = Q(k+1)-Q(k)$$
Given that we have $P$ expressed as coefficient vector. We can now solve for $q$ or $Q$ in a linear equation system containing enough of these equations, probably "enough" should be same number of equations as non-zero coefficients in $P$?
What remains is a relatively simple exercise in book-keeping. How to store and express the different quantities, what matrix performs integration $q\to Q$, and what matrix performs $Q(k) \to Q(k+1)-Q(k)$ for example.
So we can get away with calculating a polynomial $2$ times instead of $N$ times. Constant instead of linear complexity. It is worth a celebration, I think.