,

so you need to store mul[i] = (a[0] + .. + a[i]) * a[i];

ans(u, v) = mul[u] + ... + mul[v] — (a[u] + ... + a[v]) * (a[0] + ... + a[u — 1]);

so, you need to store cumSumA[i] = a[0] + ... + a[i]

cumSumM[i] = mul[0] + ... + mul[i]

ans(u, v) = cumSumM[v] — cumSumM[u — 1] — (cumSumA[u — 1]) * (cumSumA[v] — cumSumA[u — 1])

I really enjoyed doing this problem.

Let S(u, v) be the sum of all the elements in the range [u, v]. You’ll need to answer that efficiently, so you can’t walk the array everytime you need to know S(u, v).

What you’re gonna do is calculate S(0, v) for every value of v, and store that in an array of size N.

It’s quite clear that if v == 0, then S(0, v) = A[0]. Otherwise, if v > 0, then S(0, v) = S(0, v – 1) + A[v].

Walk the array and apply that formula to calculate every value of S(0, v). By the way, that’s Dynamic Programming.

Now on to S when u ≠ 0.

If you pay attention, you’ll notice that… If u == 0, then S(u,v) is just S(0, v), which you already know. If u ≠ 0, then S(u,v) = S(0, v) – S(0, u – 1). And you know those two values too, so now you can answer all queries of S(u,v) in linear time.

Next, do the same for the sum of squares in a given range (A[u]^2 + A[u+1]^2 + … + A[v]^2), and call it F(u, v). You do it exactly the same way you did with the normal sum.

Now let’s rephrase the pairwise sum …

A[u]*A[u] + A[u+1]*A[u+1] + A[u+1]*A[u] + … + A[v]*A[v] + A[v]*A[v-1] + A[v]*A[v-2] + … + A[v]*A[u]

If you do (A[u] + A[u+1] + A[u+2] + … A[v]) * (A[u] + A[u+1] + A[u+2] + … A[v]), you’ll end up having every A[x] * A[y] with x ≠ y duplicated. In other words, you have to do that multiplication, but then remove A[i]*A[i] for every i in [u,v], then divide by 2, and then add A[i]*A[i] for every i in [u,v] again. The sum of every A[i]*A[i] in [u,v] is F(u,v), which we calculated earlier, and (A[u] + A[u+1] + A[u+2] + … A[v]) is just S(u,v).

So the final answer is (S(u,v) * S(u,v) – F(u,v)) / 2 + F(u,v).

I hope I was clear enough....