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
Auto comment: topic has been updated by Aakas_kumar (previous revision, new revision, compare).
Hello, this was explained in editorial of round 891, which was prepared by my team. Nevertheless, math is pretty neat if you know how to use it)
It's nice algebra
Yup !!
Hi! there's a nice visual representation of this
but this reminds me of a proof for why certain n^3 tree dp's are actually n^2
https://codeforces.com/blog/entry/69888#comment-543684
basically if we fix node v, and let a[i] = size of v's i'th-child's subtree, then blue area represents twice the # of operations of looping over all pairs of childs, and nodes in their subtrees.
then the red area represents # of operations done when recursing on v's childs (we inductively assume ith child takes a[i]^2 operations)
size of v's subtree = 1 + a[0] + a[1] + ... + a[n-1], and area of entire square = (a[0] + a[1] + ... + a[n-1])^2 and represents work done in v's subtree
Auto comment: topic has been updated by Aakas_kumar (previous revision, new revision, compare).