Using Segment tree to perform FIND_BY_ORDER

Revision en1, by zerow, 2024-04-01 12:01:07

So I was solving a question, and in that question I basically had to find the kth available index after in each operation, and then occupy that index, basically removing it from the available indices.

Example:- Available indices : 0 1 2 3 4 5

1st Op: Find 2nd available index Ans: 1 Now available Indices: 0 2 3 4 5

2nd Op: Find 3rd available Index Ans: 3
Now available indices: 0 2 4 5

I implemented a segment tree to solve this and then applied binary search to find the index where the SUM=INDEX WE NEED TO FIND.

I just built a SUM segment tree,set the value of each node to 1, and then found the sum of segments. After each operation, I set the used index to 0 and then just updated my segment tree as such:

 // I built the SUM segment tree with each value in the array set as 1 and then calculated the SUM of SEGMENTS

        int lo=0;
        int hi=n-1;
        int ffns=hi;
        while(lo<=hi){
            int mid=(lo+hi)/2;
            int p=query(1,0,n-1,0,mid);   //the query command which returns the sum of the segment
            

            if(p<v[i].second+1){
                lo=mid+1;
            }
            else{
                hi=mid-1;
                ffns=mid;
            }

        }
    
        fns[ffns]=v[i].first;
        update(1,0,n-1,ffns,0);      // update just sets the value of the index which we found to 0

However, I feel like I could remove the binary search part and just implement the segment tree in such a way that it helps me find the kth available index without having to use binary search.

Tags implementation, segement tree, data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English zerow 2024-04-01 12:01:46 5
en1 English zerow 2024-04-01 12:01:07 1721 Initial revision (published)