Creating binary indexed tree

Question

I read various tutorials on BIT.. topcoder etc ones, all operations are well explained in those, but m not getting the way BIT is created i.e.

Given an array, 1-D, how e have to kake the corresponding BIT for that? ex. if the array is 10 8 5 9 1 what will the BIT for this?

I am a beginner, so apologies if my question sounds stupid but i am not understanding this. So, please help.

Answer 1

You simply start with an empty structure (allo 0s) and insert each element. Complexity is O(NLogN) but likely the rest of your algotihm is also NLogN so it will not matter.