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<int> 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 ↵
↵
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<int> 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 ↵
↵
