Using Segment tree to perform FIND_BY_ORDER 
Difference between en1 and en2, changed 5 character(s)
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. ↵


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)