Can prefix sums weighted by polynomial expression be done faster?

Question

I was given the following exercise:

Given a polynomial P and a real sequence x ₁ , ..., x _n , find a 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 preliminary processing performed on x ₁ , ..., x _n .

I tried to solve this problem for quite some time and did not have much success. An obvious solution requires O (n ² ) preprocessing time: for each j from 1 ... n I can calculate P (j) = a ₀ + ja ₁ + j ² a ₂ + ... + j ^m a _m in O (mn). Then I can calculate the prefix sums for any S (i, j), where j> i in O (n) time for each individual i, thus continuing in O (n ² ) time as a whole. (I just take the regular amounts of the prefix separately for each possible i.) I would like to (asymptotically) go faster than this, if possible.

The problem is that computing S (i, j) does not provide any 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? P moved to the right. If there was a way to calculate S (i + 1, j) from S (i, j), I figured I could continue in O (mn) time.

I tried:

• Calculate (regular) prefix sums for x ₁ , ..., x _n and manipulate expressions so that the regular prefix sum can be used to calculate S (i, j) without success.

• Write an explicit formula for S (i, j) and grouping the terms with polynomial coefficients (a _i 's) rather than x _i ' s. The problem remains the same.

If you can do it faster, please give me a hint on how to proceed. Please do not give clear decisions , I would like to understand myself.

PS: Actually there is a hint: "Summarize the prefix amounts."

Answer 1

You can do this with O(nm+m^2) preprocessing and memory, and the query time is O(m) . If your m limited, this is basically the time you requested.

Since you asked me not to give too direct hints, I’ll just show you how you could solve your problem if you used the simple polynomial P(x) = x .

Determine (and pre-calculate O(nm) :

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

Then we have:

 S(i,j) = Sum_{i<=k<j} (ki)*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 requests.

With a small amount of manipulation, summarizing the above takes O(m^2) query time for general polynomials. However, with additional O(nm+m^2) processing, you can move on to O(m) query time. I assume this is optimal for memory usage in linear mode n .