Why tf people are downvoting blog & instead upvoting stories about softwares engineers .

Constraints ? And it is better to give link rather than picture , as link assures that it's not from ongoing contest.

This Problem is pretty much easy if you use a segment tree.

Suppose the left child node contains answers for range [A1, A2] and the right child node contains answers for range [A3, A4] then the parent node must contain the answers for range [A1...A4] which can be obtained from the values of left child node and right child node.

Let, left child node holds, L1 = answer for their subtree [Ex:- A1, A2] L2 = subtree sum [Ex:- A1 + A2]

and, right child node holds, R1 = answer for their subtree [Ex:- A3, A4] R2 = subtree sum [Ex:- A3 + A4] Then, answer for parent node will be :- Ans = L1 + R1 + L2*R2.

The extra term L2*R2 comes because we want every element present in the left child range to form a product with every element in the right child range which in turn comes out to be L2*R2 (do some pen and paperwork, you will get that).

So, Each node of the segment tree stores two data, answer as well as the sum in their range.

Note:- I got my solution accepted in the last minute of the test.