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

History

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