nevermind_'s blog

By nevermind_, history, 9 years ago, In English

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!

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
6 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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.