Jahid's blog

Binary Index Tree
By Jahid, 10 years ago, In English

How can I quickly identify a particular problem can easily be solved by BIT? What kinds of problems can be solved by BIT other than range sum calculation & increasing sub-sequence?

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

»
10 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Well, the fact that you need cumulative sums and you can update some element in array, like you have queries sum(l,r) and update(pos,val)

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It's also possible to solve range minimum query (only with negative updates) and range maximum query (only with positive updates) with BIT.
Anyway, BIT is like set or vector ... It's just a useful tool! You can use it when you need it. You just have to keep it in your mind this thing exists and be ready to use it.

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

See this link , for understanding various usage of BIT.
http://zobayer.blogspot.in/2013/11/various-usage-of-bit.html

For problems, follow this link :-
http://ahmed-aly.com/Category.jsp?ID=26

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

You can find the number of inversions in permutation using BIT:

for(int i=N;i>=1;i--)
{
ans+=sum(A[i]);
update(A[i],1);
}

So index i is 1 if number i was already visited, otherwise it's 0. With sum(A[i]) we find the numbers less than A[i], which are on its right. If it's not a permutation, just a sequence with N distinct numbers, you can easy compress them from 1 to N in O(NlogN) using STL sort.

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

M.Mahdi thanks for your concept :) .. I never knew it .. :( hagu zobayer vai's blog is awesome and thanks to you for your information. :) P_Nyagolov thank you :)

I am trying to solve problem.

→ Reply