algorithm - 二叉索引树：为什么“i + lowBit(i)”有效？

Question

我知道如果我们想用 index 更新 node i，我们需要递归更新 node i = i + lowBit(i)，直到新值超过二叉索引树的大小。

我的问题是：如何证明i + lowBit(i)可以覆盖我们需要更新的所有节点？是否有可能存在索引j不在i + lowBit(i)链中且满足的节点j > i && j - lowBit(j) + 1 <= i？

提前致谢。

标签： algorithmbinary-indexed-tree