CODEWITHSUNDEEP
arraysalgorithmmathoptimization
Sanchit Kumawat
Sanchit Kumawat

Reputation: 33

Finding the sum of products of first and last elements in a range, second and second last and so on using segment tree

We are given array of 'n' integers and we are given queries in the form (l,r) where l and r are indices in range 'n'. For each query the answer is
Suppose the array is a={a1,a2,a3,a4,a5,a6,a7...} and the query is (2,7) then for this query it should give a2*a7+a3*a6+a4*a5
This means that first element is multiplied with the last in the query range, second is multiplied by second last element and so on.
Length of each query is divisible by 2
Is there any way to do this using segment tree>

Upvotes: 3

Views: 180

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65508

Here's an O(k n log n + q (n/k))-time solution (so if q = Θ(n) we set k = √(n/log n) to get O(n √(n log n))).

The key ingredient is a fast convolution algorithm, perhaps based on FFT, though per djb and probably others, in the n = 1e5 range, you might get better results from an asymptotically slower algorithm. If we convolve the input array with itself, we get (e.g., for a 9-element array):

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

Already the odd coefficients are closely related to some of the possible answers to queries (e.g., c9/2 is the answer to (1,8)).

Our approach is to compute the self-convolution of k-1 prefixes of the array and k-1 suffixes (actually we only need the odd coefficients, not that this is an asymptotic speedup), i.e., 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]. To answer a query (l,r), we select a good subarray, grab the self-convolution coefficient at index l+r, divide it by two, and fix it up by adding O(n/k) terms.

Rather than write this precisely in mathematical notation, let me give an example. Suppose n = 9 and k = 3 and we want to answer the query (2,7). We grab the coefficient

c9 = a3*a6 + a4*a5 + a5*a4 + a6*a3

for the subarray a[1..6] and return

c9/2 + a2*a7.

What's the best subarray? If l+r <= n, then we should round r down to r' a multiple of n/k and use a[1..r']. Otherwise we should round l up to l' a multiple of n/k and use a[l'+1..n].

Upvotes: 2

Related Questions