I was going through this tutorial ( https://www.topcoder.com/…/data-sc…/binary-indexed-%20trees/ ) about binary index tree or fenwick tree. But not getting what does the tutorial actually mean for f[i], c[i] & MaxVal. Can anybody explain it with an example? Thanks in advance!
Basically, f is an arbitrary array of size MaxVal, and c is defined by the formula. Neither f nor c are stored explicitly, instead we manipulate them through tree array.
I know the post is old but it is for those who have same doubt...
MaxVal ==> value of maximum i for which f[i] is nonzero.
f[i] ==> the frequency by which ith event is occuring.
c[i] ==> the sum of f[i]+f[i-1]+...+f[1] ==> prefix sum.
tree[] ==> stores the fenwick tree.