# 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:** 1\
**Showing post:** 2

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

---

_[View the full topic](https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277)._