我们得到了'n'整数的数组，我们得到了形式为(l，r(的查询，其中l和r是范围'n'中的索引。对于每个查询，答案是
假设数组是a={a1，a2，a3，a4，a5，a6，a7…}如果查询是(2,7(，那么对于这个查询，它应该给出a2*a7+a3*a6+a4*a5
这意味着第一个元素乘以查询范围中的最后一个，第二个元素乘以倒数第二个，依此类推。
每个查询的长度可以被2整除
有什么方法可以使用段树>
这里有一个O(k n log n+q(n/k((-时间解(所以如果q=Θ(n(，我们设置k=√(n/log n(得到O(n√(n log n((。
关键因素是快速卷积算法，可能基于FFT，尽管在n=1e5范围内，每个djb和其他可能的算法，你可能会从渐进较慢的算法中获得更好的结果。如果我们将输入数组与其本身进行卷积，我们得到(例如，对于9元素数组(：
c2 = a1*a1
c3 = a1*a2 + a2*a1
c4 = a1*a3 + a2*a2 + a3*a1
c5 = a1*a4 + a2*a3 + a3*a2 + a4*a1
c6 = a1*a5 + a2*a4 + a3*a3 + a4*a2 + a5*a1
c7 = a1*a6 + a2*a5 + a3*a4 + a4*a3 + a5*a2 + a6*a1
c8 = a1*a7 + a2*a6 + a3*a5 + a4*a4 + a5*a3 + a6*a2 + a7*a1
c9 = a1*a8 + a2*a7 + a3*a6 + a4*a5 + a5*a4 + a6*a3 + a7*a2 + a8*a1
c10 = a1*a9 + a2*a8 + a3*a7 + a4*a6 + a5*a5 + a6*a4 + a7*a3 + a8*a2 + a9*a1
c11 = a2*a9 + a3*a8 + a4*a7 + a5*a6 + a6*a5 + a7*a4 + a8*a3 + a9*a2
c12 = a3*a9 + a4*a8 + a5*a7 + a6*a6 + a7*a5 + a8*a4 + a8*a3
c13 = a4*a9 + a5*a8 + a6*a7 + a7*a6 + a8*a5 + a9*a4
c14 = a5*a9 + a6*a8 + a7*a7 + a8*a6 + a9*a5
c15 = a6*a9 + a7*a8 + a8*a7 + a9*a6
c16 = a7*a9 + a8*a8 + a9*a7
c17 = a8*a9 + a9*a8
c18 = a9*a9
奇数系数已经与查询的一些可能答案密切相关(例如，c9/2是(1,8)的答案(。
我们的方法是计算数组的k-1前缀和k-1后缀的自卷积(实际上我们只需要奇数系数，而不是渐进加速(，即a[1..n/k], a[1..2n/k], ..., a[1..(k-1)n/k]; a[n/k+1..n], a[2n/k+1..n], ..., a[(k-1)n/k+1..n]。为了回答查询(l,r)，我们选择一个好的子阵列，获取索引l+r处的自卷积系数，将其除以2，并通过添加O(n/k(项来固定它。
与其用数学符号来精确地写，不如让我举一个例子。假设n = 9和k = 3，并且我们想要回答查询(2,7)。我们获取系数
c9 = a3*a6 + a4*a5 + a5*a4 + a6*a3
用于子阵列a[1..6]并返回
c9/2 + a2*a7.
什么是最好的子阵列？如果是l+r <= n，那么我们应该将r四舍五入到r'——n/k的倍数，并使用a[1..r']。否则，我们应该将l四舍五入到l'——n/k的倍数，并使用a[l'+1..n]。