SPOJ.com - Problem MKTHNUM

You have given an array…You have to find the kth number in a range?How can I solve it with Merge sort tree.I build the merge sort tree?but then what?From various blog I found they apply binary search on X.How the Binary search will work for this solution?

Store array elements with its indices (eg. B[i]={A[i],i} ) then sort B. Now build merge sort tree (MST) over array B. Divide left and right child in MST on the basis of value of element but keep list of indices in each node of MST. This way, you store for a node (responsible for value b/w a and b ) ,list of index (sorted due to MST) of elements with value b/w a and b.
Now while querying, (l,r,k), let there be p elements in left child of a node with indices b/w l and r. If p>=k, kth number will be in left child else query (l,r,k-p) in right child.
To find p, we do binary search over list of index in a node to find no. of indices b/w l and r. p=upperbound( r )-lowerbound( l ) ->in left child.

1 Like

Can you provide the best blogs,or best tutorial for mergesorttree(mst)

This article : Merge Sort Tree Tutorial

This comment: MKTHNUM Implementation

This article and implementation helped me learn Merge Sort Tree.

1 Like

Thans for the link