在给定的数组中，找到区间L到R的值。

Given array A, and two indexes L and R,find the value of

给定数组A和两个索引L和R，求值。

Summation(AS[i]*AS[j]*AS[k])

求和([我]*[j]*[k])

where L<=i<j<k<=R holds, and AS is the sorted set of all elements of A in range L to R inclusive.

其中L<=i

Example: Let A=(4,4,1,6,1,3) L=0 and R=3 gives AS=(1,4,6), so Ans=1*4*6=24

例子:让A=(4,4,1,6,1,3) L=0, R=3给出=(1,4,6)，所以Ans=1*4*6=24。

I don't have any approach better than O(n^3) , which is very slow. Please suggest me some faster approach.

我没有任何方法比O(n ^ 3),这是非常缓慢的。请给我推荐一些更快的方法。

Number of elements in A are upto 10^5.

的元素数量高达10 ^ 5。

1 个解决方案

#1

As the question commentators said, determining AS can be done by using a hash table H. You simply iterate through the elements of A from index L to R and you insert each element into H. The result should be the set of elements you need. You still need to sort the set. For that you maybe copy the elements of H into an array and sort that array. The result is AS. This should take no more than O(NlogN) steps, where N=R-L.

正如评论员所说，可以通过使用哈希表来确定，您只需遍历从索引L到R的元素，然后将每个元素插入到h中，结果应该是您需要的元素集。你仍然需要对集合进行排序，因为你可能会将H元素复制到一个数组中，并对数组进行排序。结果是。这应该不超过O(NlogN)步骤，其中N=R-L。

What the commentators did not say is how to compute the sum efficiently. It can be done in O(N) steps. Here is how.

评论者没有说的是如何有效地计算和。它可以在O(N)步骤中完成。以下是我的解释。

We first make the following observation:

我们首先做如下观察:

Sum(AS[j]*AS[k], a <= j < k <= b) = 
   1/2*(AS[a] + AS[a+1] + ... + AS[b])^2 - 
   1/2*(AS[a]^2 + AS[a+1]^2 + ... + AS[b]^2)

We expand our target sum as follows:

我们扩大目标金额如下:

S = Sum(AS[i]*AS[j]*AS[k]) = 
   AS[L]   * Sum(AS[j]*AS[k], L+1 <= j < k <= R) +     (iteration     1)
   AS[L+1] * Sum(AS[j]*AS[k], L+2 <= j < k <= R) +     (iteration     2)
   ...
   AS[R-2] * Sum(AS[j]*AS[k], R-1 <= j < k <= R).      (iteration R-L-1)

We now apply the observation.

我们现在应用观察。

To determine the sums of the form Sum(AS[j]*AS[k], a <= j < k <= b) efficiently we can first compute

为了确定形式和的和(AS[j]*AS[k]， a <= j <= b)，我们可以首先计算。

S1 = AS[L] + AS[L+1] + ... + A[R]
S2 = AS[L]^2 + AS[L+1]^2 + ... + A[R]^2

and then incrementally subtract the first term from each sum as we iterate through the elements of AS from from index L to R-2.

然后，当我们对从L到R-2的元素进行迭代时，从每个和中减去第一个项。

Thus, determining the sum you want can be done in O(N) steps after you determine AS. Provided that you use some comparison sort method the whole algorithm should take O(|A|) + O(NlogN) + O(N) steps.

因此，确定您想要的总和可以在您确定之后的O(N)步骤中完成。如果使用某种比较排序方法，整个算法应该采用O(|A|) + O(NlogN) + O(N)步骤。

#1