Introduction

If the weight is a polynomial in the index, you can usually do much better than evaluating the polynomial from scratch for every query. The key idea is to split the polynomial into powers of the index and precompute one prefix array per power.

The Algebra Behind the Speedup

Suppose you want:

W(r) = sum from i = 0 to r of A[i] * P(i)

and the polynomial is:

P(i) = c0 + c1 * i + c2 * i^2 + ... + cd * i^d

Then:

W(r) = c0 * S0(r) + c1 * S1(r) + c2 * S2(r) + ... + cd * Sd(r)

where each Sk(r) is just:

Sk(r) = sum from i = 0 to r of A[i] * i^k

So instead of recomputing the whole weighted sum each time, you precompute the prefix sums for each power once.

Precompute Power-Weighted Prefix Arrays

For a fixed polynomial degree d, build d + 1 prefix arrays:

• one for A[i]
• one for A[i] * i
• one for A[i] * i^2
• and so on up to A[i] * i^d

Then any polynomial-weighted prefix query becomes a short linear combination of those prefix values.

1class PolynomialPrefix:
2    def __init__(self, values, degree):
3        self.degree = degree
4        n = len(values)
5        self.prefix = [[0] * (n + 1) for _ in range(degree + 1)]
6
7        for i, value in enumerate(values):
8            power = 1
9            for k in range(degree + 1):
10                self.prefix[k][i + 1] = self.prefix[k][i] + value * power
11                power *= i
12
13    def weighted_prefix(self, r, coeffs):
14        total = 0
15        for k, c in enumerate(coeffs):
16            total += c * self.prefix[k][r + 1]
17        return total
18
19
20values = [3, 1, 4, 1, 5]
21pp = PolynomialPrefix(values, degree=2)
22
23# P(i) = 2 + 3i + i^2
24print(pp.weighted_prefix(4, [2, 3, 1]))

This preprocessing takes O(n * d), and each query takes O(d).

Why This Is Faster

If you answer many queries with the same maximum polynomial degree, the savings are substantial. The naive approach recomputes all weighted terms for every query, which is O(n * d) per query or worse if the polynomial evaluation is written poorly.

With the prefix approach:

• preprocessing is O(n * d)
• each prefix query is O(d)
• each range query is also O(d) by subtraction

For fixed degree, that is effectively linear preprocessing and constant-time query work with respect to the array length.

Range Queries Are Easy Too

If you want a weighted sum on [l, r] rather than [0, r], subtract the stored prefixes:

1def weighted_range(pp, left, right, coeffs):
2    total = 0
3    for k, c in enumerate(coeffs):
4        total += c * (pp.prefix[k][right + 1] - pp.prefix[k][left])
5    return total
6
7
8print(weighted_range(pp, 1, 3, [2, 3, 1]))

This works as long as the polynomial is expressed in the original global index i. If the query uses a shifted polynomial such as P(i - l), then you need an extra binomial-expansion step, but the same precomputed power prefixes still help.

What You Cannot Beat

There is an important limit: if the array itself is arbitrary, you still need at least O(n) input work to read it. So there is no magical sublinear preprocessing for the general case. The real optimization is reducing repeated query work, not avoiding the initial pass over the data.

Also, if the polynomial degree changes wildly or becomes large, the d + 1 prefix arrays may become expensive. This method is best when the degree is small and fixed.

Common Pitfalls

• Recomputing the polynomial value from scratch for each query position.
• Forgetting that one prefix array is needed per power of the index.
• Mixing global-index weighting with shifted-index weighting without adjusting the math.
• Calling the naive method O(n^2) when the real baseline is often O(n * d) for degree d.
• Using this technique when the polynomial degree is so large that the preprocessing itself dominates.

Summary

• Polynomial-weighted prefix sums can be accelerated by precomputing one prefix array per power of the index.
• For degree d, preprocessing is O(n * d) and each query is O(d).
• Range queries are just prefix subtraction.
• The method is most effective when the polynomial degree is small and reused across many queries.
• For general arrays, you cannot avoid the initial O(n) pass over the data.