Indian Computing Olympiad

Training Material


Range queries

Range queries with interval updates and interval queries

Next we consider the situation where we have both interval updates and interval queries.

Paint (revisited)

A painter paints a strip N squares wide

            ----------------------
           | 1 | 2 | 3 | .... | N |
            ----------------------
      

In one step, the painter paints a continuous strip from square i to square j, which we denote [i,j]. Periodically, we want to answer the following query:

minlayers([i,j]) among all squares in the interval [i,j], report the minimum number of layers among the squares in this interval

How do we efficiently answer these queries?

Recall that we recorded the paint strokes in a segment tree.

                              [1,8]
                 _______________|________________
                |                                |
              [1,4]                            [5,8]
         _______|_______                _________|________
        |               |              |                  |
      [1,2]           [3,4]          [5,6]              [7,8]
     ___|___         ___|___        ___|___            ___|___
    |       |       |       |      |       |          |       |
  [1,1]   [2,2]   [3,3]   [4,4]  [5,5]   [6,6]      [7,7]   [8,8]
      

At each vertex v, when we apply a layer of paint, we record

coats(v) = number of paint strokes that contain the entire interval Interval(v), but do not contain the entire interval Interval(parent(v)) spanned by the parent of v.

The number of coats at an interval is given by the value at this node and the values of intervals that include this one (these are above).

We need to store more information at each node to answer minlayer queries. What is the structure of this information and how do we use it to answer queries?

Suppose we keep the following additional information at each node: for each interval v, how many full coats of v have come from coats directly across v (but not the next bigger interval spanning v) or by adding up coats over subintervals of v? For children l and r of v, if we inductively know this value, add the minimum of the two to coats(v).

below(v) = number of paint strokes that span the interval Interval(v), either directly, or made up of smaller strokes.
= coats(v) + min(below(leftchild(v)),below(rightchild(v)))

Now, with each stroke you walk down and update coats(v), below(v) and then walk back up and recompute below(w) for each w on the path above v.