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 !