Prefix sums weighted by a polynomial expression, can you do faster?

Question

I have been given the following exercise:

Given polynomial P and a real sequence x₁, ..., x_n, find data structure D that can evaluate expressions of the form S(i, j) = P(0)x_i + P(1)x_{i + 1} + ... + P(j - i - 1)x_{j - 1} in constant time with some preprocessing done on x₁, ..., x_n.

I have been trying to solve it for quite some time now and have not had much of a success. An obvious solution requires O(n²) preprocessing time: for every j in 1 ... n, I can calculate P(j) = a₀ + ja₁ + j²a₂ + ...+ j^ma_m in O(mn) time. Then I can calculate prefix sums for any S(i, j) where j > i in O(n) time for each distinct i, thus proceeding in O(n²) time altogether. (I am just taking regular prefix sums separately for every possible i.) I would like to go (asymptotically) faster than this, if possible.

The problem seems to be that the calculation of S(i, j) yields no useful information about S(i + 1, j). Look: S(i, j) = P(0)x₁ + P(1)x₂ + ..., but S(i + 1, j) = P(0)x₂ + P(1)x₃. See? The P's have moved right. If there was a way to calculate S(i + 1, j) from S(i, j), I believe I could proceed in O(mn) time.

I have tried:

• Calculate (regular) prefix sums for x₁, ..., x_n and manipulating the expressions so that the regular prefix sum could be used to calculate S(i, j) with no success.

• Write the explicit formula for S(i, j) and grouping the terms by polynomial coefficients (a_i's) rather than by x_i's. The problem remains the same.

If you can do faster, please, give me a hint how to proceed. Please do not give explicit solutions, I would like to figure it out myself.

P.S.: There is a hint given, actually, to solve this: "Generalize prefix sums."

Answer 1

You can do this with O(nm+m^2) preprocessing and memory, and O(m) query time. If your m is bounded, that is basically that running time you were asking for.

Since you asked not to be given too direct hints, I will just show you how you might solve your task, if you were using the simple polynomial P(x) = x.

Define (and precalculate in time O(nm):

Q0(j) = Sum_{0<=k<j} x_k
Q1(j) = Sum_{0<=k<j} k*x_k

We then have:

S(i,j) = Sum_{i<=k<j} (k-i)*x_k
       = Sum_{i<=k<j} k*x_k - i*Sum_{i<=k<j} x_k
       = Q1(j)-Q1(i) - i*(Q0(j)-Q0(i))

For constant time queries.

With a bit of sum manipulation, the generalization of the above takes O(m^2) time per query for general polynomials. However with an additional O(nm+m^2) preprocessing you can get down to O(m) query time. I conjecture this is optimal for memory usage linear in n.