So, I have a list of intervals, say on a real line,
let intervals = [(1, 12), (2, 5), (3, 24), (7, 8)]
Please note that I use parentheses only because I store them as pairs, the intervals are actually included (closed).
And I have a list of points,
let points = [13, 2, 7, 3, 14]
I am trying to count the number of points falling into each interval, it should be the [Integer]length of which length intervals,
counts == [3, 2, 4, 1]
Now the problem is that both intervalsare pointsreally long, so using an iterative receiving algorithm O(length intervals * length points)will last forever. Thus, I am considering using some kind of segment tree to make it O(log (length intervals) * length points). I am currently watching the SegmentTree package . However, my limited knowledge of Haskell was not enough for me to come up with a complete solution.
I understand that if the goal was to count the number of intervals spanning each point, then the solution is straightforward:
import qualified Data.SegmentTree as S
map (S.countingQuery $ S.fromList intervals) points
But I can’t think of a way to do the opposite. It seems to me that in order to do this efficiently, you need to use a mutable data structure, and this will just open the Pandora mailbox.
What could be the solution?