Indian Computing Olympiad

Range Queries→Mobiles (IOI 2001)

Suppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S×S matrix with the rows and columns numbered from 0 to S-1. Each square contains a base station. The number of active mobile phones inside a square can change because a phone is moved from a square to another or a phone is switched on or off. At times, each base station reports the change in the number of active phones to the main base station along with the row and the column of the matrix.

Write a program, which receives these reports and answers queries about the current total number of active mobile phones in any rectangle-shaped area.

We need a two dimensional version of a binary indexed tree.

BIT[x,y] stores the sum of the rectangle bounded by x-2^k....x and y-2^l...y where k is the number of trailing zeros in x and l is the number of trailing zeros in y

    |
    |       ((x-2k)+1,y)               (x,y)
    |            o------------------------o
    |            |                        |
    |            |                        |
    |            |                        |
    |            |                        |
    |            o------------------------o
    |       ((x-2k)+1,                (x,(y-2l)+1)
    |        (y-2l)+1)
    |
    |
     ----------------------------------------------------
      

To compute segment sums, we compute prefix sums with respect to the starting position. In the two dimensional version, for every point (x,y) we would like to calculate the sum in the rectangle from (0,0) to (x,y). Call this sum Rect(x,y).

If we start with BIT[x,y] we get the rectangle above. The next rectangle to its left is stored in BIT(next(x),y). The next rectangle below is BIT(x,next(y)). In this way, by walking back applying next() repeatedly in each coordinate, we can tile the space from (0,0) to (x,y) with rectangles whose values are stored in BIT. There are log N rectangles in each dimension, so there are log² N rectangles overall in this tiling.

    |
    |                  ((x-2k)+1,y)          (x,y)
    | ...  o-----o------------o-------------o
    |      |     |            |             |
    |      |     |BIT[x-2k+1, |  BIT[x,y]   |
    | ...  | ... |    y]      |             |
    |      |     |            |             |
    |      o-----o--------------------------o (x,(y-2l)+1)
    |      |  .  |BIT[x-2k+1, | BIT[x,      |
    | ...  |  .  |    y-2l+1] |     y-2l+1] |
    |      o-----o------------o-------------o
    |        ..        ...          ...
     ----------------------------------------------------
      

So, we have

Rect(x,y)

=

Sum i in {x, next(x),...} j in {y, next(y),...}

BIT[i,j]}

If we update a value A[x,y], we can update all affected values BIT[x,y] by walking up throught Unext(x), Unext(Unext(x)),... and Unext(y), Unext(Unext(y)),... independently in each coordinate.

As in the 1 dimensional case, we can build the initial 2-D indexed tree by starting with 0's everywhere and updating the initial values one by one. This takes time N² (log N)².

---