我最近学习了 Fenwick Tree (Binary Indexed Tree)数据结构。
在查询时，我能理解为什么要减去(idx & -idx)。 但是，我真的不明白为什么在更新值时要添加 (idx & -idx)。
换句话说，我知道我们必须更新所有会受到更新某个元素 x 影响的区间，而且我知道 BIT[x] 是第一个被更新的，但无法理解为什么下一个索引要更新的是 BIT[x + (x & -x)]
谢谢。
最佳答案
这里有一个很好的解释:http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
关键思想是，如果 f(i) 是索引 i 处的频率，则 t(i) 是所有 (i - (r - 1)) .. i 的累积频率，其中 r 是最小设置位在我。您可以将 r 计算为 r = i & -i。
[编辑:上面我错误地将 (r - 1) 写成了 (2^r - 1)。]
例如，如果 i = 12 = 1100_2，则 r = 100_2 且 t(i) = f(1001_2) + f(1010_2) + f(1011_2) + f(1100_2) = f(9) + f( 10) + f(11) + f(12)。
当从 0 .. i 计算累积频率时，您实际上是对 i 处的 t 值求和，i 的最小设置位已删除，i 的至少两个设置位已删除，...等等，直到我们用完位。
例如，如果 i = 12 = 1100_2，那么我们需要 t(1100_2) + t(1000_2)。
因此，如果您更改 f(i) 处的值，则必须更改所有受影响的 t 值。这些是 t(i), t(i + r), 2t(i + r), 4t(i + r), ... 等等，直到我们超过最后一个索引。这些正是我们将检查的受影响的 t 值，用于索引 j >= i 的任何累积频率计算。
[编辑:修复了最后一段中的“受影响的 t 值”序列，以响应 j_random_hacker 的更正。]
关于algorithm - 二叉索引树(Fenwick Tree)——关于更新，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11874701/