Moving Up a Dimension - Part 1

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(nlog²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's vector just stores the values of that range in sorted order.During queries just traverse the segment tree like we usually do but when we are on a terminal node, binary search on the vector of that node to check how many values are less than the given parameter K. When going up, merging the answers means just adding the values.

Persistance : This is also a classic problem for persistent segment tree, and normally most MST(merge sort tree and not minimum spanning tree) problems can be reduced to Persistence. However there ARE many problems in which persistence can't be used. Persistence is very well documented and I won't be going over it.

Dynamic Segment Tree

Another version of segment tree that is not very commonly known but is very useful is the dynamic segment tree. In the vanilla version, the main problem was that we declared the memory beforehand in a array and so, if the range of input was near to 1e9, we could not create a segment tree on it. (Considering coordinate compression isn't feasable). In dynamic segment tree what we do is we allocate the memory as and when needed. When we are traversing the segment tree, if its specific child which we want to visit wasn't created before, we create it then and there. Since this means it wasn't visited before, creating it at that moment dosen't really change anything. Why does this help? Well overall, even if the range of input is very high, the input size itself is bounded by 1e5 in most cases. Moreover, we visit only about O(nlogn) nodes only and hence memory overall is nlogn. Obviously this is using pointers. (However, if we want to avoid pointers, we can also create a buffer array and then keep the indices as children "pseudo-pointers".)

Accommodating Updates In MergeSort Tree

In the MST, the problem was that if we tried to update a value in our array, we were doomed, because that would mean we would need to merge logn times, which would be very bad because, just merging at the head node would take O(N) time since we would go through both the whole vectors again.

This is why instead of a vector, we often keep a set inside the nodes. This way, while making a modification, we can just add and remove a single element in each of the logn visited nodes -- No need to merge the whole node-sets again!

But then, sets are awfully restrictive. Not much can be done using the inbuild set functions. And it would be quite a job to implement my own set class.

Mixing Of Segment Tree

Now, with the adequate knowledge, we can combine both the structures that I have told -- The MST and the dynamic segment tree.

What we do is, instead of keeping a set in the nodes of the merge sort tree, we keep a dynamic segment tree. Obviously we can still maintain the same space complexity as in a dynamic segtree, only the required memory is allocated. Hence, since in a single "row" of the segtree, overall space that would have been taken by the vector in the MST was O(n) {again, refer to the merge sort proofs} the dynamic segtree that will be created on this would also take the same amount of space. Moreover, all other functionality is preserved so answering queries also requires the same time. 

Sure, this will be an overkill in most problems, but I have mentioned it because it is MUCH more versatile than a MST with sets. 

Problem Type:

The problems that can be solved using these are queries of the type 

"Given a range L to R in the query, Find all numbers such that *some condition* is satisfied. Here in our segment tree we will traverse to find the corresponding terminal nodes for that range L to R and then query that condition in the vector/set/dynamic segment tree that is contained in those terminal nodes.

With this the prerequisite knowledge is done. Part-2 will be about...