I've recently learned the Fenwick Tree (Binary Indexed Tree) data structure.
When querying , I can understand why to subtract (idx & -idx). However, I can't really understand why to add (idx & -idx) when updating a value.
In other words, I know we have to update all intervals which will be affected by updating some single element x , and I know that BIT[x] is the first to be updated , but can't understand why the next index to be updated is BIT[x + (x & -x)]
Thanks.
Here's a good explanation: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
The key idea is that if f(i) is the frequency at index i, then t(i) is the cumulative frequency for all (i - (r - 1)) .. i where r is the least set bit in i. You can calculate r as r = i & -i.
[EDIT: above I had incorrectly written (r - 1) as (2^r - 1).]
For example, if i = 12 = 1100_2, then r = 100_2 and t(i) = f(1001_2) + f(1010_2) + f(1011_2) + f(1100_2) = f(9) + f(10) + f(11) + f(12).
When calculating the cumulative frequency from 0 .. i, you essentially sum the t values at i, i with its least set bit removed, i with its least two set bits removed, ... and so forth until we run out of bits.
For example, if i = 12 = 1100_2, then we want t(1100_2) + t(1000_2).
Consequently, if you change the value at f(i), you must change all the affected t values. These are t(i), t(i + r), 2t(i + r), 4t(i + r), ... and so forth until we exceed the last index. These are precisely the affected t values we would examine for any cumulative frequency calculation for index j >= i.
[EDIT: fixed the 'affected t values' sequence in the last paragraph in response to a correction by j_random_hacker.]