I have given a boolean array and have to answer some queries [l, r]. the query is what is the first and last position of 1 in the given range. (Note : the array is changing from time to time i.e. in this array we are also given a query of [l, r] which means we have to turn off all the 1 in this range, so, it want online solution)
I am able to solve it in (log(N))^2 per head by using binary search and segment tree. But it didn’t scale well so wants to know more efficient method i.e. log(N). please help !
For each node in the segment tree, store the smallest and largest index containing a ‘1’ in the range for that node, you can take min/max of child nodes to get these values for each node. Let’s call those two indexes as left and right. Whenever you need to query, return the minimum of all the lefts and maximum of all the rights that you find in the nodes for your range. Whenever you get an update ie., to change all 1s in a range to 0, set left=inf and right=-1, use lazy propagation.
