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.