Help In Range Query

suppose that we are given m segments like [[l1,r1],[l2,r2],…[lm,rm]] where 1<=li<=ri<=n and
n=2e5,m=2e5.
suppose q queries are given each of form L1,R1 where 1<=Li<=Ri<=n ,1<=q<=2e5.
can we find in o(1)or o(logn) for each query whether Li,Ri covers atleast one out of m given segments i.e Li<=lj&&Ri>=rj for atleast one j.
if anyone knows about it or has any idea please help
@carre
@ssjgz
@galencolin or anyone who knows about it please help

build array max_ending_before[n] like this:

       max_ending_before[i] = -1 (for i in [1,n])
       for i=1 to m
           max_ending_before[Ri] = max(max_ending_before[Ri],Li)
       for i=2 to n
           max_ending_before[i] = max(max_ending_before[i],max_ending_before[i-1],)

Now you can ans each query in O(1) just looking if max_ending_before[Rq]>=Lq

1 Like

Although @carre solution is much more efficient than mine, I would share an O(log(n)) approach. Sort the coordinates [l_i, r_i] according to l_i first. Then in each query you can find the smallest j(using upper/lower bound) such that L_i \leq l_j. The only thing now left is to check whether there is some k in [j, n] such that r_k \leq R_i. So you just need to store the suffix minimum, that is:

 suffixmin[i] = min(suffixmin[i+1], r[i])

Therefore when you have calculated the index j in the discussion above just check if suffixmin[j] \leq R_i.
One advantage of this solution is that it does not require the constraint 1 \leq l_i \leq r_i \leq n. It works for any lower/upper bounds on the values.

1 Like

thanks i will make sure sure that i try both the approches as they both are equivalently good