Given an array A, we compute a new array BIT that stores sums of some segments of A. Here is an example.
i : 1 2 3 4 5 6 7 8 A : 2 3 1 3 6 2 1 4         BIT: 2  1  6  1  < Store A[i] for odd i \  \  \   + \  +  +  5  8  < \  \  \ Store segment  9  \  <  sums as shown, \ \   explained formally  +  below  / 22 <
What is stored at in BIT[i]?
Write out the positions in binary:
i : 0001 0010 0011 0100 0101 0110 0111 1000 A : 2 3 1 3 6 2 1 4
Let k be the number of trailing zeros in binary representation of i. In BIT[i], we store the sum of the segment of length 2^{k} at position i.
Assuming we can do this, how do we use this data to compute prefix sums?
Suppose we want the prefix sum A[1] + A[2] + … + A[i].
We know that the sum of some segment to the left of i is stored in BIT[i], depending on the binary representation of i.
We can compute the biggest j ≤ i such that j lies outside this segment. Call this value next(i). We then pick up BIT[next(i)] and again compute the biggest k to the left of the segment stored in BIT[next(i)] etc
How do we compute this value?
Suppose i has k trailing 0's. It looks like 


The number we want is i  2^{k}. But 2^{k} is 


So, i  2^{k} is just 

So, if we start with i, next(i) can be computed by flipping the last 1 in the binary represenation of i to a 0. The prefix sum we want is
BIT[i] + BIT[next(i)] + BIT[next(next(i))] + …
We stop when we reach a position that is all 0's.
Each time we go from BIT[i] to BIT[next[i]], we flip one 1 to 0. The binary representation of i has log N bits, so we can iterate the next() operation at most log N times.
How do we update this data structure when we get an instruction of of the form Update(i,a)?
We have to update BIT[i] and some BIT[j] for some j > i. Which values of j are affected?
Clearly, odd values of j are unchanged, since they only refer to intervals of length 1.
Suppose, again that i is of the form
x 1 00000 
<k> 
Let j =
y 1 00000 
<r> 
y 0 00000 
<r> 
So, to find the next position j such that BIT[j] includes i, we have to find the next position to the right of i that has at least k trailing zeros. This must be i + 2^{k}. Again, 2^{k} is
1 00000 
<k> 
Call this value Unext(i). From Unext(i) we go to Unext(Unext(i)) etc. At each step, the number of trailing zeros in Unext(j) is one more than in j, so we only need to update log N entries.
What remains is to compute next(i) and Unext(i) efficiently.
Since next(i) is i  2^{k} and Unext(i) is i + 2^{i}, this boils down to computing 2^{k} for a given i, where k is the number of trailing zeros.
We start with i, which is 


If we flip all bits, we get 


Now add 1. We get i', where i' is 


Now, we take a bitwise AND of i and i' and get 

which is 2^{k}.
Note that flipping all bits and adding 1 generates the 2's complement, which is the way (i) is represented in all computers. So, we can obtain 2^{k} by doing the bitwise AND of i and (i)!
How do we build the binary indexed tree to start with?
Assume that A consists of all 0's initially, so A[i] = BIT[i] = 0 for all i. Do N updates to insert the initial values of A[i], 1 ≤ i ≤ N, into the tree. This takes N log N time.
©IARCS 2012–2016
PÄ›stujeme web  visit: Skluzavky