output the kth smallest number in sub-array between l and r.

https://practice.geeksforgeeks.org/problems/easy-query3301/1?page=1&category[]=Segment-Tree&sortBy=submissions

You are given an array nums of size n and q queries. Now for each query of the form l, r and k, output the kth smallest number in sub-array between l and r.

Example 1:
Input: nums = {4, 1, 2, 2, 3},
Query = {{1, 5, 2}, {3, 5, 3}}
Output: {2, 3}
Explanation: For the 1st query 2nd smallest in
[1, 5] is 2. For the 2nd query 3rd smallest in
[3, 5] is 3.

Example 2:
Input: nums = {1, 2, 3, 4, 5},
Query = {{2, 5, 1}}
Output: {2}
Explanation: The 1st smallest in [2, 5] is 2.

---------------------------------------------------------------------------------------------------------------------------------------
// UNOPTIMISED SOLUTION

class Solution {
private:
    static int const MXN=15000;
    vector<int> tree[4*MXN+1];
    unordered_map<int,int> ranker;
    unordered_map<int,int> de_ranker;
public:
    vector<int> Rankify(vector<int> &nums){
        vector<int> temp=nums;
        sort(temp.begin(),temp.end());
        for(int i=0;i<nums.size();i++){
            if(ranker.find(temp[i])==ranker.end()){
                ranker[temp[i]]=i;
                de_ranker[i]=temp[i];
            }
        }
        for(int i=0;i<nums.size();i++){
            temp[i]=ranker[nums[i]];
        }
        return temp;
    }

    int De_Rankify(int index){
        return de_ranker[index];
    }

    vector<int> MERGE(vector<int> &arr1, vector<int> &arr2){
        vector<int> res;
        int n=arr1.size();
        int m=arr2.size();
        int i=0;
        int j=0;
        while(i<n && j<m){
            if(arr1[i]<arr2[j]){
                res.push_back(arr1[i++]);
            }
            else{
                res.push_back(arr2[j++]);
            }
        }
        while(i<n){
            res.push_back(arr1[i++]);
        }
        while(j<m){
            res.push_back(arr2[j++]);
        }
        return res;
    }

    void buildTree(vector<int> &nums, int start, int end, int parent){
        if(start>end){
            return;
        }
        if(start==end){
            tree[parent]={nums[start]};
            return;
        }
        int mid=(start+end)/2;
        buildTree(nums,start,mid,2*parent+1);
        buildTree(nums,mid+1,end,2*parent+2);
        vector<int> leftChild=tree[2*parent+1];
        vector<int> rightChild=tree[2*parent+2];
        vector<int> root=MERGE(leftChild,rightChild);
        tree[parent]=root;
    }

    int LessThanEle_InRange(int start, int end, int parent, int qstart, int qend, int element){
        if(qstart>end || qend<start){ // no elements
            return 0;
        }
        if(qstart<=start && qend>=end){ // count elements less than element
            return upper_bound(tree[parent].begin(),tree[parent].end(),element)-tree[parent].begin();
        }
        int mid=(start+end)/2;
        int left=LessThanEle_InRange(start,mid,2*parent+1,qstart,qend,element);
        int right=LessThanEle_InRange(mid+1,end,2*parent+2,qstart,qend,element);
        return left+right;
    }

    bool isOK(int element, int k, int n, int l, int r){
        int count=LessThanEle_InRange(0,n-1,0,l,r,element);
        return count>=k;
    }

    int QUERY_ANSWER(int l, int r, int k, int n){
        int low=0;
        int high=n-1;
        int res=-1;
        while(low<=high){
            int mid=(low+high)/2;
            if(isOK(mid,k,n,l,r)==true){ // if this mid element is the >=kth element, reduce mid
                res=mid;
                high=mid-1;
            }
            else{
                low=mid+1;
            }
        }
        return De_Rankify(res);
    }

    vector<int> FindQuery(vector<int> &nums, vector<vector<int>> &Query){
        int n=nums.size();
        vector<int> temp=Rankify(nums);
        buildTree(temp,0,n-1,0);
        vector<int> res;
        for(auto q: Query){
            int ans=QUERY_ANSWER(q[0]-1,q[1]-1,q[2],n);
            res.push_back(ans);
        }
        return res;
    }
};


---------------------------------------------------------------------------------------------------------------------------------------

// OPTIMISED

class Solution {
private:
    static int const MXN=15000;
    vector<int> tree[4*MXN+1];
public:
    vector<int> MERGE(vector<int> &arr1, vector<int> &arr2){
        vector<int> res;
        int n=arr1.size();
        int m=arr2.size();
        int i=0;
        int j=0;
        while(i<n && j<m){
            if(arr1[i]<arr2[j]){
                res.push_back(arr1[i++]);
            }
            else{
                res.push_back(arr2[j++]);
            }
        }
        while(i<n){
            res.push_back(arr1[i++]);
        }
        while(j<m){
            res.push_back(arr2[j++]);
        }
        return res;
    }

    void buildTree(vector<pair<int,int>> &nums, int start, int end, int parent){
        if(start>end){
            return;
        }
        if(start==end){
            tree[parent]={nums[start].second};
            return;
        }
        int mid=(start+end)/2;
        buildTree(nums,start,mid,2*parent+1);
        buildTree(nums,mid+1,end,2*parent+2);
        vector<int> leftChild=tree[2*parent+1];
        vector<int> rightChild=tree[2*parent+2];
        vector<int> root=MERGE(leftChild,rightChild);
        tree[parent]=root;
    }

    int getKthIndex(int start, int end, int parent, int qstart, int qend, int k){
        if(start==end){
            return tree[parent][0];
        }
        int mid=(start+end)/2;
        int L=lower_bound(tree[2*parent+1].begin(),tree[2*parent+1].end(),qstart)-tree[2*parent+1].begin();
        int R=upper_bound(tree[2*parent+1].begin(),tree[2*parent+1].end(),qend)-tree[2*parent+1].begin();
        int elements=R-L;
        if(elements>=k){ // if more than k elements exist in left child, move left
            return getKthIndex(start,mid,2*parent+1,qstart,qend,k);
        }
        return getKthIndex(mid+1,end,2*parent+2,qstart,qend,k-elements);  // if less than k elements exist on left side, go right, but search for the (k-elements)th element, because, there were elements element on left side, so reduce count from side side
    }

    vector<int> FindQuery(vector<int> &nums, vector<vector<int>> &Query){
        int n=nums.size();
        vector<pair<int,int>> a;
        for(int i=0;i<n;i++){
            a.push_back({nums[i],i});
        }
        sort(a.begin(),a.end());
        buildTree(a,0,n-1,0);
        vector<int> res;
        for(auto q: Query){
            int ans=nums[getKthIndex(0,n-1,0,q[0]-1,q[1]-1,q[2])];;
            res.push_back(ans);
        }
        return res;
    }
};