Merge Sort Tree - Tutorial

[suvro_coder]

Check out my post about point updates in merge sort tree.

Point Updates in Merge Sort Trees

Hello, I have implemented the version of merge sort tree that can handle point updates and supports duplicate elements in the tree. I have done it using C++ STL: Policy based data structures. There is no implemented tree multiset in STL. So, I have used pair<T,int> as a key where the second element in pair is the time when item has been added, in order to maintain uniqueness of elements. The time complexity summaries are as follows : Build Complexity — O(n log^2 n) Query Complexity …