Indian Computing Olympiad

Range queries

Range queries with static updates

Suppose we want to efficiently compute the minimum value for arbitrary intervals (i,j) in a static array.

We precompute some information, as follows:

  2   6   5   8   9   7   11  12  <-- Initial array

  2   6   5   8   9   7   11  12  <-- Minimum in intervals of length 1 starting at i
  2   5   5   8   7   7   11      <-- Minimum in intervals of length 2 starting at i
  2   5   5   7   7               <-- Minimum in intervals of length 4 starting at i
  2                               <-- Minimum in intervals of length 8 starting at i

Similarly, we can keep track of the minimum in intervals whose length is a power of 2 ending at i.

  2   6   5   8   9   7   11  12  <-- Initial array

  2   6   5   8   9   7   11  12  <-- Minimum in intervals of length 1 ending at i
      2   5   5   8   7    7  11  <-- Minimum in intervals of length 2 ending at i
              2   5   5    7   7  <-- Minimum in intervals of length 4 ending at i
                               2  <-- Minimum in intervals of length 8 ending at i

Now, suppose we ask for the minimum value in the range A[i]...A[j]. Find the largest k such that i+(2^k-1) does not cross j. The segments A[i]....A[2^k] and A[j-2^k]...A[j] must overlap. Then,

min(A[i]...A[j]) is min{ min(A[i]..A[i+2^k]), min(A[j-2^k]..A[j]) }

The two quantities we need are already available in the tables we have precomputed, so all the work goes into computing the table.

Notice that the first row in the table is immediate—just copy the array.

From row i, we can compute row i+1 in linear time—the minimum over an interval of 2^k+1 starting at i is the minimum of the two intervals of size 2^k in previous row starting at i and i+2^k.

Clearly the table has log N rows for an array of size N. We spend linear time to compute each row, so we can build the table in time N log N. (Actually, if we only count the values actually computed, each row is half the length of the previous row, so the overall time is really only N).