Reputation: 75
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