我最近学习了Fenwick Tree（二进制索引树）数据结构。
查询时，我可以理解为什么要减去（idx & -idx）。但是，我真的不明白为什么在更新值时要添加 (idx & -idx)。
换句话说，我知道我们必须更新所有将受到更新某些单个元素 x 影响的间隔，并且我知道 BIT[x] 是第一个要更新的，但不明白为什么要更新下一个索引是 BIT[x + (x & -x)]
谢谢。
问问题
1614 次
1 回答
1
这是一个很好的解释： http: //community.topcoder.com/tc ?module=Static&d1=tutorials&d2=binaryIndexedTrees
关键思想是，如果 f(i) 是索引 i 处的频率，则 t(i) 是所有 (i - (r - 1)) .. i 的累积频率，其中 r 是 i 中设置最少的位。您可以将 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), ... 等等，直到我们超过最后一个索引。这些正是我们将在指数 j >= i 的任何累积频率计算中检查的受影响的 t 值。
[编辑：修复了最后一段中的“受影响的 t 值”序列，以响应 j_random_hacker 的更正。]
于 2012-08-09T06:31:59.240 回答