SegmentTree.hs

-----------------------------------------------------------------------------
-- |
-- Module      :  Squares.BruteForce
-- Copyright   :  (c) Dmitry Astapov 2010
-- License     :  BSD-style
-- Maintainer  :  dastapov@gmail.com
-- Stability   :  experimental
-- Portability :  portable
--
-- SegmentTree-based stabbing query
-----------------------------------------------------------------------------
module Stabbing.SegmentTree (counts) where

import Data.SegmentTree

-- Optimized stabbing count:
-- use segment tree parametrized with (Monoid Integer) to count hits for each query point.
--
-- For "n" intervals and "m" points:
--   tree construction takes O(n log n)
--   each lookup takes O(log n), thus all lookups take O(m log n)
-- Total complexity: O ((max m n) log n)
counts :: [(Rational, Rational)] -> [Rational] -> [Integer]
counts intervals points = map (countingQuery segmentTree) points
  where 
    segmentTree = fromList intervals