我们得到了“n”个整数的数组，我们得到了 (l,r) 形式的查询，其中 l 和 r 是“n”范围内的索引。对于每个查询，答案是
假设数组是 a={a1,a2,a3,a4,a5,a6,a7...} 并且查询是 (2,7) 那么对于这个查询它应该给出a2*a7+a3*a6+a4*a5
这意味着首先元素乘以查询范围中的最后一个，第二个乘以倒数第二个元素，依此类推。
每个查询的长度可以被 2 整除
有没有办法使用分段树来做到这一点>
1 回答
2
这是一个 O(kn log n + q (n/k)) 时间解（所以如果 q = Θ(n) 我们设置 k = √(n/log n) 得到 O(n √(n log n)） ）。
关键成分是快速卷积算法，可能基于 FFT，尽管根据 djb 和可能的其他算法，在 n = 1e5 范围内，您可能会从渐近较慢的算法中获得更好的结果。如果我们将输入数组与自身进行卷积，我们会得到（例如，对于一个 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].
于 2020-11-11T13:05:49.040 回答