Coding Start Up!

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

Merge-Sort Tree I'll start with this because this is quite useful, but does not have much material on it in the internet. The construct is simple enough. First, build a normal segment tree Wait! don't finish building it :P . Instead of store a single value in a node, we store a vector of values. When we merge two nodes, we do a 2-ptr on the vectors to build our resultant vector so that the sorted order is preserved. During queries, we just go down to our terminal nodes and usually do a binary search on the values. Proof of space and time complexity of building is very similar to merge sort. Query time is O(n log² n) (since we normally do an extra binsearch in each of the terminal nodes, which there are O(logn) overall) Just to give an example, suppose we are given an array of size N and there are Q queries each of which gives a L,R and K and asks how many values in range L to R are less than K. For this, first create a merge-sort tree where each node...