Indian Computing Olympiad

Training Material

Range queries

Binary index tree

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 2k 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   
x 1 00000
    <-k->
The number we want is i - 2k. But 2k is 
  1 00000
    <-k->
So, i - 2k is just 
x 0 00000
    <-k->

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->
. Suppose we walk right to position j whose binary representation has r trailing 0's, r < k.

Let j = 

 y 1 00000
     <-r->
. The leftvalue value stored in BIT[j] stops short of the value 
 y 0 00000
     <-r->
, so this excludes i for sure.

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 + 2k. Again, 2k is 

 1 00000
   <-k->
, so we add this quantity to i.

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 - 2k and Unext(i) is i + 2i, this boils down to computing 2k for a given i, where k is the number of trailing zeros.

We start with i, which is 
 x  1  00000
       <-k->
If we flip all bits, we get 
 x  0  11111
       <-k->
Now add 1. We get i', where i' is 
 x  1  00000
       <-k->
Now, we take a bitwise AND of i and i' and get 
 0  1  00000
       <-k->

which is 2k.

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 2k 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.

Basic topics

Advanced topics