┌───────┴───────┐ │ ┌─┴

┌───────┴───────┐ │

┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ │

有了 lowbit，我们就能在完全二叉树里快速地定位：

我们知道，索引的本质就是预先存储一些信息，现在我们来看如何从原数组 A 来构建我们的二叉索引数 BIT 。我们定义：

看公式好像很复杂，我们拆解一下。看到下标 i - lowbit(i) + 1，我们知道代表了 i 所在节点左子树的底层节点。我们用图来说明如何计算 BIT[12] (图中标 x)

┌───────┴───────┐

┌───┴───┐ ┌───┴───┐

┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐

所以说 sum(k) 操作就是求节点 k 及它的父节点的和。

可以有多种方式初始化，每种的复杂度不同。