通过多项式表达式加权的前缀和,你能做得更快吗？

Question

我接受了以下练习:

给定多项式P和实数序列x ₁,...,x _n,找到可以计算形式S(i,j)= P(0)x _i + P(1)x _{i + 1的}表达式的数据结构D. + ... + P(j - i - 1)x _{j - 1}在恒定时间内对x ₁,...,x _n进行一些预处理.

我一直试图解决它已经有一段时间了,并没有取得多大成功.一个显而易见的解决方案需要为O(n ²)预处理时间:每Ĵ在1 ... N,我可以计算P(j)的=α ₀ + JA ₁ + J ²一个₂ + ... + J ^米一_米在O(mn)时间.然后,我可以计算任何S(i,j)的前缀和,其中对于每个不同的i,在O(n)时间中j> i,从而完全在O(n ²)时间内进行.(我只是为每一个可能的i分别取常规前缀和.)如果可能的话,我想(渐近地)比这更快(渐近).

问题似乎是S(i,j)的计算不产生关于S(i + 1,j)的有用信息.看:S(i,j)= P(0)x ₁ + P(1)x ₂ + ...,但S(i + 1,j)= P(0)x ₂ + P(1)x ₃.看到？在P的已经转移的权利.如果有办法从S(i,j)计算S(i + 1 ,j),我相信我可以在O(mn)时间内进行.

我试过了:

• 计算x ₁,...,x _n的(常规)前缀和并操纵表达式,以便可以使用常规前缀和来计算S(i,j)但没有成功.

• 写出S(i,j)的显式公式,并用多项式系数(a _i)而不是 x _i对这些项进行分组.问题依然存在.

如果你能做得更快,请给我一个提示如何继续.请不要给出明确的解决方案,我想自己搞清楚.

PS:实际上有一个提示可以解决这个问题:"通用前缀总和."

Answer 1

您可以通过O(nm+m^2)预处理、内存和O(m)查询时间来做到这一点。如果您的m运行时间是有限的，那么这基本上就是您要求的运行时间。

由于您要求不要给出过于直接的提示，因此我将仅向您展示如果您使用简单的多项式 ，您将如何解决您的任务P(x) = x。

定义（并及时预先计算O(nm)：

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

然后我们有：

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))

用于恒定时间查询。

通过一些求和操作，上述O(m^2)一般多项式的每次查询都需要时间。然而，通过额外的O(nm+m^2)预处理，您可以减少O(m)查询时间。我猜想这对于n.