# Calculating number of intersections of a horizontal line with line segments efficiently

I'm given an array $$A = [a_1, a_2, ....a_n]$$ using which I construct $$n-1$$ contiguous line segments by drawing a line from $$(i,a_i)$$ to $$(i+1, a_{i+1})$$. Now, I'm given $$q$$ queries in the form of $$x_1, x_2, y, l, r$$ where $$l$$ and $$r$$ are the range for the array $$A$$ and the rest indicate a horizontal line segment $$L$$ from $$(x_1, y)$$ to $$(x_2, y)$$. For each query, I want to find total intersections of $$L$$ and the segments in the range $$l$$ and $$r$$ in $$O(q)$$ or $$O(q\log{n})$$ complexity so that total computational complexity becomes: $$O(n + q)$$ or $$O(n + q\log{n})$$

I was able to arrive at a solution that works in $$O(nq)$$ which simply traverses each range and calculates whether $$L$$ intersects with the segments or not.
I believe, some pre-processing can be done on $$A$$ which can reduce the complexity.
• Can you clarify what you want to compute, exactly? The number of intersections of each query can be $\Omega(n)$, so just listing the intersections can take $\Omega(nq)$ time. Are you just interested in the number of intersections? Do you know all the queries beforehand? Is $O(n + q)$ the total time that you want to spend to answer all the queries? (You say that you want to spend $O(n+q)$ tine "for each query", and it is a bit odd that this complexity depends on $q$). – Steven Mar 16 at 0:33
• @Steven I want to compute, total number intersections of the line $L$ with the segments in the range provided. Yes, I know all the queries beforehand. Yes, $O(n+q)$ is the total time I want to spend on the queries – Kunal Gupta Mar 16 at 7:31
• @Steven It seems to me each query can only have 1 intersection, if I understood this correctly. The input array is not $n$ arbirary points, rather its the $n$ points $(i, a_i)$ for $i$ between $1$ and $n$. – 6005 Mar 16 at 16:16