Moving Up a Dimension - Part 2

Overlapping Ranges

First, suppose we have the following problem:

• We are given some ranges of the form [L,R]
• For each query we will be given a range [QL,QR] and we will have to report the count of all the ranges that lie completely within this range.
• In an update, we can add/delete a new range

Main Idea: 

The main idea that is not easy to come up with, and could seem as being an overkill for this but is useful for a variety of problems, of which this example is just a simple case.

We are given ranges in a 1D numberline. The crux is that we want to convert these ranges from a 1D line segment to a 2D point. How? Well, for each range that we are given [L,R] just define a point as (x=L,y=R). Thus the updates are basically just adding or deleting points. And the queries? Well, define the query as a point P(Ql,Qr). Now we just have to count the number of points whose X-coordinate is more that that of P and whose Y-coordinate is less than that of P. Thus forming a query-rectangle, whose upper left corner is P and whose base is the x axis. Note that this rectangle is unbounded in the right side, but this is not much of a problem as we ARE given the maximum X-Coordinate anyway.

Note that all this is just for visualization. In reality, we don't really require a core 2D structure like a 2D segment tree or quadtree. Just the structures we talked about in the previous post -- mergesort trees.

Implementation:

(For simplicity I will assume that all the x-coordinates are distinct. Extending this to the general form is easy and should be attempted. )

First sort all the points by X coordinate. Now, create a mergesort trees, where the index of the underlying array should be treated as the x-coordinate and the values of the index should be considered as the Y-coordinate. So, our rectangle query is just a query from the indices Ql to end where we count the number of values whose value is less than Qr.

Thus, we are effectively handling 2 separate query bounds at once :

• One bound is for the X-coordinate which we handle by restricting the range in the merge sort tree that we query upon 
• the second for the y coordinate which we handle by passing a parameter in the internal query. The internal sets are then queried using this parameter to find the count of elements.

 Note that in this case we indeed will be using sets in the internal nodes as we also have to handle the additions and deletions during update operations.

Changing More 1D stuff to 2D

This codechef problem is also an example how to use this idea of moving up a dimension.

Initial Idea:

Here, first suppose that the constraint max(0,....) wasnt there. Then we could have summed up the value of A[L to R] and B[L to R] and then multiplied them with C and D to get the answer. Not much of a problem. So we will try to get the problem to the same form first!

2Dfying it:

Now, it can be noticed that the formula is given in the terms of a cross-product!

More specifically, if the cross product of the point P(A,B) with the point Q(C,D) is positive then add it to the sum. Now we know that cross product between two vectors is proportional to the sin of the angle inbetween. Again, it can be verified that if we treat the two points P and Q as vectors starting from the origin, then the cross product is positive only if the vectors are in anticlockwise orientation. 

This can be modelled again as a 2D problem :  given a query point we have to consider only the points which are in an anticlockwise position wrt the query point-vector. This can again be handled using a mergesort tree where we, instead of sorting the inner sets according to y, we will sort by the angle created with the X-axis by the vector joining that point to the origin. 

Note that the indices of the mergesort tree will be according to the increasing X axis.

Yet Another Problem!

Suppose we are given a problem where given an array and Q queries, in each query we have to find the number of distinct elements in the range [L,R].

This problem has a very standard solution using Mo's algorithm. However I would want to discuss a segment tree solution.

Solution: The transformation here is a bit tough to come up with. We will consider the points as P(current index, previous index which had the same value) for each current index. 

How does this help? Note that for all distinct values, this means that the Y-coordinate of the correspoinding point will be less than L !

So the rectangle query is just from index x=L to x=R, how many points are there such that the y coordinate is less that L. 

Implementation? MergeSortTree again! We sort the indices initially by x-coordinate and the internal sorting of the vectors inside the node is by the y coordinates. 

Concluding: 

I hope these demonstrations have been helpful as to how we can effectively convert a 1D object to a 2D point and then query on these points rather than on the usual data that can be a bit hard. Hope this helps!