Query regarding binary indexed tree (or Fenwick Tree)

Revision en1, by ivplay, 2019-08-23 15:17:06

What is the proof that from any index idx , idx + (idx&-idx) is the next closest index that covers idx? I mean how can I prove that no other index in range ( idx,idx+(idx&-idx) ) actually covers idx? '(' means exclusive and covers idx means contains information of idx ??

Thanks in advance.

Tags advanced data structure, binary indexed tree, proof


  Rev. Lang. By When Δ Comment
en1 English ivplay 2019-08-23 15:17:06 346 Initial revision (published)