SPOJ: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?
TIA…
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.
MKTHNUM(MST)
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