I was looking at the segment tree template of tourist. It doesn't have any operation for find the k'th zero or k'th one. So I wondered if is it possible to the with the current template without changing it. My question is : Is it possible to use find last and find first operations to find the k'th zero or one? I mean just using the current template to answer that kind of queries.Any ideas? If not what is the best ways to implement it for the current template so that we don't have to change the code a lot each time.
You can see the template of tourist here .
You would need to keep the number of zeros/ones in each node, and then you can find the first prefix s.t. there are >=k zeros/ones.