Hi folk: I know it is not a very hard concept like HLD and merging in the trees and all but for the junta that is below specialist/people but it could give a great inside when you ask all pair sum problems it could be a subproblem of the hard and bigger problem.

here is code for O(n^2)

int sum=0; vector v(n); for(int i=0; i<n; i++){ for(int j= i+1; j<n; j++){ sum+= v[i]*v[j]; } }

so here is the code for the O(n)

int sum=0; int sq_sum=0; for(int i=0; i<n; i++){ sum+=v[i]; sq_sum+= v[i]*v[i]; } int ans = (sum*sum — sq_sum)/2 ; it may be a good concept