# Merge Sort Tree - Tutorial

**URL:** <https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277>\
**Category:** tutorial\
**Tags:** merge-sort-tree, segment-tree, sorting\
**Created:** [March 27, 2017, 8:07pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277 "2017-03-27T20:07:29Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![arunnsit](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arunnsit/32/249610_2.png) [@arunnsit](https://discuss.codechef.com/u/arunnsit)\
**Post date:** [March 27, 2017, 8:07pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/1 "2017-03-27T20:07:29Z")

</div>

**Prerequisites** : Segment Trees

**Target Problem** : Given an array of N elements and you have to answer Q queries of the form L R K , To Count the numbers smaller than K in range L to R.

**Key Idea** : The key idea is to build a Segment Tree with a vector at every node and the vector contains all the elements of the subrange in a sorted order . And if you observe this segment tree structure this is some what similar to the tree formed during the merge sort algorithm ( Yes , thats why they are called Merge Sort Trees ) .

**Building the tree :**

```
vector<int>tree[5*N];
int A[N];
Void build_tree( int cur , int l , int r )
{
     if( l==r )
     {
            tree[cur].push_back( a[l] );
            return ;
     }
     int mid = l+(r-l)/2;
     build_tree(2*cur+1 , l , mid ); // Build left tree 
     build_tree(2*cur+2 , mid+1 , r ); // Build right tree
     tree[cur] = merge( tree[2*cur+1] , tree[2*cur+2] ); //Merging the two sorted arrays
}

```

**Querying the tree :**

```
int query( int cur, int l, int r, int x, int y, int k)
{
       if( r < x || l > y )
      {
               return 0; //out of range
      }
      if( x<=l && r<=y )
      {
              //Binary search over the current sorted vector to find elements smaller than K

              Return lower_bound(tree[cur].begin(),tree[cur].end(),K)-tree[cur].begin();
      }
      int mid=l+(r-l)/2;
     return query(2*cur+1,l,mid,x,y,k)+query(2*cur+2,mid+1,r,x,y,k);
}

```

**Build function Analysis** : Build a merge sort tree takes O(NlogN) time which is same as Merge Sort Algorithm . It will take O(NlogN) memory because each number Ai will be present in at most LogN vectors (Height of the tree ) .

**Query function Analysis** : A range L to R can divided into at most Log(N) parts, where we will perform binary search on each part . So this gives us complexity of O(LogN \* LogN) per query .

**Handling Point Updates** : The only reason that we cant handle updates on MST in this code is because its merge function takes too much time, so even if theres a point update it will lead to O(N). So the major issue is of vectors and rearranging them on updations, but why do we need vectors ? Just to find the elements smaller than K in that complete vector, right ? Lets forget about vectors and keep [policy based data structure](http://codeforces.com/blog/entry/11080) at each node which handles three queries (insertion , deletion and elements smaller than K in the set) in O(LogN) time . So now no need to rearrange vectors and we can use insertion - deletion to handle point queries . This is just an idea , we can discuss this in comments again if anyone has a doubt .

**Bonus** :  
How to use this to solve the query of type Kth smallest number in range L to R ? So we can binary search over the solution and find the value which has exactly K numbers smaller than it in the given range . Complexity : O(LogN \* LogN \* LogAi ) per query .

**Why to use MST:** Apart from the code simplicity, they answer queries online . We could have used some offline algorithms like MOs or even Segment tree but come on, Online Querying is great because it can be used in Dp Optimisations and stuff like that . Peace Out .

---

<div class="post-metadata">

**Author:** ![likecs](https://discuss.codechef.com/user_avatar/discuss.codechef.com/likecs/32/1496_2.png) [@likecs](https://discuss.codechef.com/u/likecs)\
**Post date:** [March 28, 2017, 12:33am UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/2 "2017-03-28T00:33:44Z")

</div>

You can do Kth smallest number query in range L to R, in O(n \* {\log}^{2}n) by building the merge sort tree on indices instead of the values. This solution doesn’t depend on the values of A[i], however large they may be.

For implementation details, one may refer to [this code](http://ideone.com/T4gxB9) for [MKTHNUM](http://www.spoj.com/problems/MKTHNUM/) problem on Spoj.

---

<div class="post-metadata">

**Author:** ![sinbycos](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sinbycos](https://discuss.codechef.com/u/sinbycos)\
**Post date:** [April 28, 2017, 8:35am UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/3 "2017-04-28T08:35:09Z")

</div>

I’m confused… Why would the complexity have a factor of logAi in the “Bonus” part. I can only think of a O(q\*log^3 n) solution. Binary search over the array and find the value that has k-1 smaller numbers in O(log^2 n).

Also, would appreciate if you could upvote me. Need karma points 😛  
Thanks!

---

<div class="post-metadata">

**Author:** ![rajarshi\_basu](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rajarshi_basu/32/244428_2.png) [@rajarshi\_basu](https://discuss.codechef.com/u/rajarshi_basu)\
**Post date:** [April 28, 2017, 6:13pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/4 "2017-04-28T18:13:47Z")

</div>

how can you handle updates here…?

---

<div class="post-metadata">

**Author:** ![s1\_73](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@s1\_73](https://discuss.codechef.com/u/s1_73)\
**Post date:** [May 31, 2017, 7:54pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/5 "2017-05-31T19:54:25Z")

</div>

For the bonus part, consider a _query(L,R,X)_, and _X=R-L+1_, which means that you need to find out the maximum number from the range _L_ to _R_. According to your solution, we can binary search on _Ai_, and find out which number gives _number of numbers \<= Ai_ to be X. But how will you keep a track of _Ai_s which are present in the range _[L,R]_ of the original array _A_? This is needed because for the case where you need to find the maximum in a range _[L,R]_, any number _Y_ lying between the maximum number from _[L,R]_ and the next maximum in the array _A_ will also yield _X_ as the answer to the _query(L,R,Y)_.

---

<div class="post-metadata">

**Author:** ![manjrekarom29](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@manjrekarom29](https://discuss.codechef.com/u/manjrekarom29)\
**Post date:** [June 21, 2017, 8:20am UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/6 "2017-06-21T08:20:52Z")

</div>

For elements of size 10^5 ill have to define vector tree[log2(10^5) \* 10^5] right?

It’s giving me runtime error for such big chunk of memory in c++.

Please clarify! Thanks!

---

<div class="post-metadata">

**Author:** ![lukecavabarret](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@lukecavabarret](https://discuss.codechef.com/u/lukecavabarret)\
**Post date:** [July 2, 2017, 5:17pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/7 "2017-07-02T17:17:18Z")

</div>

We can achieve much better. First, we compress the array in order to contain only values in range [0,N). We keep a table to associate a compressed value to the original one in O(1) and associate a normal value to his lower\_bound in compressed range in O(logN). This take us so far NlogN. Then we build a Persistent Segment Tree, where for every time i we have stored the frequencies of each value in the array with index smaller or equal to i, and every node store the sum of the two sons. Overall is NlogN preprocessing.  
Every time we want to know how many integers there are in range [l,r] smaller than k, we do as follows:

- first we replace k with the compressed value of the greater original value smaller than k. //logN
- We query the Persistent Segmentent Tree in the interval [0,k], assuming that the value written in each node is the one of the tree® - tree(l-1).

In the end we use NlogN space and time complexity for preprocessing, and each query take logN. But we can do a lot of amazing other stuff, for example, being asked about the k-th smallest value in range [l,r], and answer in logN as well.

---

<div class="post-metadata">

**Author:** ![parth\_patel15](https://discuss.codechef.com/user_avatar/discuss.codechef.com/parth_patel15/32/4269_2.png) [@parth\_patel15](https://discuss.codechef.com/u/parth_patel15)\
**Post date:** [January 7, 2018, 6:33pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/8 "2018-01-07T18:33:30Z")

</div>

Can anyone help me in the spoj problem [MKTHNUM](http://www.spoj.com/problems/MKTHNUM/) and tell me why I am getting wrong answer? [MY SOLUTION](https://ideone.com/sqKKVQ)

---

<div class="post-metadata">

**Author:** ![arunnsit](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arunnsit/32/249610_2.png) [@arunnsit](https://discuss.codechef.com/u/arunnsit)\
**Post date:** [May 7, 2017, 3:56am UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/9 "2017-05-07T03:56:37Z")

</div>

yes, you are correct too. thats one way to see it. if you binary search over the array it will come out to be O(q_log^3 n). but if you binary search over the a[i] value then it comes out to be O(q_log^2 n\*log ai).

---

<div class="post-metadata">

**Author:** ![arunnsit](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arunnsit/32/249610_2.png) [@arunnsit](https://discuss.codechef.com/u/arunnsit)\
**Post date:** [May 7, 2017, 3:58am UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/10 "2017-05-07T03:58:21Z")

</div>

i have already mentioned about point updates. is there anything that you didnt understand?

---

<div class="post-metadata">

**Author:** ![arunnsit](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arunnsit/32/249610_2.png) [@arunnsit](https://discuss.codechef.com/u/arunnsit)\
**Post date:** [June 3, 2017, 2:07pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/11 "2017-06-03T14:07:01Z")

</div>

i think you aren’t clear about binary search, we will binary search for the smallest number that satisfies the above condition i.e. for query(L,R,X), and X=R-L+1.find out the smallest number which gives number of numbers \<= Ai to be X. Theres no need to track its presence in array.

---

<div class="post-metadata">

**Author:** ![sinbycos](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sinbycos](https://discuss.codechef.com/u/sinbycos)\
**Post date:** [June 9, 2017, 8:25am UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/12 "2017-06-09T08:25:10Z")

</div>

But that’s only better if ai \< N, right?

---

<div class="post-metadata">

**Author:** ![mayank12559](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@mayank12559](https://discuss.codechef.com/u/mayank12559)\
**Post date:** [June 14, 2017, 10:30pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/13 "2017-06-14T22:30:05Z")

</div>

@likecs I have written the exactly same solution as you did, but in java. I am getting TLE. Can you please help me?  
Note : I am using the fast I/O also.  
Link to my code : [pHN7Z2 - Online Java Compiler & Debugging Tool - Ideone.com](http://ideone.com/pHN7Z2)

---

<div class="post-metadata">

**Author:** ![likecs](https://discuss.codechef.com/user_avatar/discuss.codechef.com/likecs/32/1496_2.png) [@likecs](https://discuss.codechef.com/u/likecs)\
**Post date:** [June 15, 2017, 12:39am UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/14 "2017-06-15T00:39:42Z")

</div>

@mayank12559, I tried to optimise your solution by making the binary serach iterative as well, but no sucess. May be the time limits of the problem are strict for java for passing with O(log^2n) approach. Also, only 4 solutions in java for this problem till date. May be you can try with C++.

---

<div class="post-metadata">

**Author:** ![mayank12559](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@mayank12559](https://discuss.codechef.com/u/mayank12559)\
**Post date:** [June 15, 2017, 8:22am UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/15 "2017-06-15T08:22:47Z")

</div>

Thanks for the reply. I will try to write the same in c++. Java solution should also get accepted though, as c++ solutions are getting accepted with same complexity. There should not be any discrimination among languages.

---

<div class="post-metadata">

**Author:** ![mayank12559](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@mayank12559](https://discuss.codechef.com/u/mayank12559)\
**Post date:** [June 15, 2017, 4:54pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/16 "2017-06-15T16:54:33Z")

</div>

@likecs I have written the code in c++. On submission I am getting Wrong Answer now. Can you please help me once again?  
Link to my code : [qC2tVy - Online C++ Compiler & Debugging Tool - Ideone.com](http://ideone.com/qC2tVy)

---

<div class="post-metadata">

**Author:** ![arunnsit](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arunnsit/32/249610_2.png) [@arunnsit](https://discuss.codechef.com/u/arunnsit)\
**Post date:** [June 22, 2017, 6:15pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/17 "2017-06-22T18:15:29Z")

</div>

Why do you think log2(10^5) \* 10^5 vectors are required? vectors should be equal to number N+N/2+N/4+N/8…(i.e number of nodes in segtree) Which is 2_N but we require a number which is multiple of 2 and greater than 2_N. So to be on safe side we usually take 4\*N nodes in segtree.

---

<div class="post-metadata">

**Author:** ![manjrekarom29](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@manjrekarom29](https://discuss.codechef.com/u/manjrekarom29)\
**Post date:** [June 23, 2017, 8:24am UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/18 "2017-06-23T08:24:37Z")

</div>

Oh yes! I got confused. Thanks

---

<div class="post-metadata">

**Author:** ![arunnsit](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arunnsit/32/249610_2.png) [@arunnsit](https://discuss.codechef.com/u/arunnsit)\
**Post date:** [July 6, 2017, 1:13pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/19 "2017-07-06T13:13:21Z")

</div>

yeah, Persistent Segment Tree can solve such problems but do you think its as easy to explain and understand as this?

---

<div class="post-metadata">

**Author:** ![lukecavabarret](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@lukecavabarret](https://discuss.codechef.com/u/lukecavabarret)\
**Post date:** [July 19, 2017, 10:20pm UTC](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277/20 "2017-07-19T22:20:45Z")

</div>

maybe. After all, the only important things -after understand segment tree in its pointer implementation- are:  
-In each update, at most logN node change  
-In each update, create a new version of all nodes changed

[Next page](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277.md?page=2)