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.
Auto comment: topic has been updated by zerow (previous revision, new revision, compare).
Go to EDU above, go to segment tree section. There's the solution of finding the kth one which is what you need here
No way man, I had tried that but just made a small error in my code which was giving a different value from what I needed. Thanks for the quick comment!