rajat1603's blog

Binary Indexed Tree -> Binary search in logn
By rajat1603, 9 years ago, In English

Hello , i want to know how to do a binary search for something ( like lowerbound for a value ) on a binary indexeded tree in (log ( n ) ) . On a segment tree it can be done in Log ( N ) but on binary indexed tree the naive binary search is LOG^2 ( n ) . So does anyone know how to make it in Log(n) ? thanks in advance .

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

»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Well, if you implement both log(n) with ST and log2(n) with BIT you will be quite surprised seeing which one is faster.

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

I do know :)

Here is my old article on this topic link

→ Reply