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. ↵
↵
↵
↵
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. ↵
↵
↵
