ihainan
ihainan

Reputation: 75

Binary Indexed Tree: Why does "i + lowBit(i)" work?

enter image description here

I know that if we want to update node with index i, we need to recursively update node i = i + lowBit(i) until the new value exceeds the size of the binary indexed tree.

My question is: how to prove that i + lowBit(i) can cover all the nodes we need to update? Is it possible that there's a node with index j which is not in the i + lowBit(i) chain and satisfies j > i && j - lowBit(j) + 1 <= i?

Thanks in advance.

Upvotes: 3

Views: 289

Answers (0)

Related Questions