Find sum of modified subarray

Given an array A of n elements.
a_i denotes i th element. We have to find the sum -

(n) \times (a_1 \times a_1 + a_2 \times a_2 + \cdots +a_n \times a_n) +
(n - 1)(a_1 \times a_2 + a_2 \times a_3 + \cdots +a_{n-1} \times a_n) +
(n - 2)(a_1 \times a_3 + a_2 \times a_4 + \cdots +a_{n-2} \times a_n) + \cdots
\vdots

1 \leq n \leq 10^5
1 \leq a_i \leq 10^9

How to solve it? Please help

2 Likes

You can make a prefix sum of the array A and also store the sum of the series

S = a1 + 2 \times a2 ++ n \times an

If we take the first term of each term of the sum, it can be written as

n \times a1 (a1 + a2 + . . .+ an) - a1 (a2 + 2 \times a3 ++ (n - 1) \times an)

Its first term can be calculated in O(1) using prefix sum and the second term can be calculated by subtracting sum of all the elements from S. So now S becomes

S = a2 + 2 \times a3 ++ (n - 1) \times an

Now we calculate second term of each term of the sum which is

n \times a2 (a2 + a3 + . . .+ an) - a2 (a3 + 2 \times a4 ++ (n - 2) \times an)

which again can be calculated in O(1) using prefix sum for the first term and subtracting that sum from S. This should be done for every element in the sum. So the entire solution becomes O(n).

If you still have a doubt feel free to ask. Hope this helps.

3 Likes

Purely Brilliant. Nice Math :slight_smile:

Thanks for nicely explained and beautiful answer