我们得到了“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))).
关键成分是 fast convolution algorithm ，也许基于 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 处获取自卷积系数，将它除以二，并通过添加 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] .
关于arrays - 使用线段树查找范围内第一个和最后一个元素、倒数第二个和倒数第二个元素的乘积之和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/64771627/