Haskell Range Minimum Query

gistfile1.hs

import Data.List.Split
import qualified Data.Vector as V

rmqBuild :: [Int] -> (Int, V.Vector Int)
rmqBuild xs =
    let l = length xs
        n = until (\ x -> x >= l) (*2) 1
        inf = maxBound :: Int
        f ys = map minimum $ chunksOf 2 ys
    in (n ,V.fromList $ concat $
        until (\x -> (length  (head x)) == 1)
        (\(y:ys) -> ((f y):y:ys)) ([xs ++ take (n - l) [inf, inf..]]))

rmqQuery n tree a b = rmqQuery' tree a b 0 0 n
    where
      rmqQuery' tree a b k l r =
          if r <= a || b <= l
          then maxBound
          else if a <= l && r <= b
               then tree V.! k
               else min (rmqQuery' tree a b (2 * k + 1) l ((l + r) `div` 2))
                        (rmqQuery' tree a b (2 * k + 2) ((l + r) `div` 2) r)

main = do
  contents <- getContents
  let ds = lines contents
      (n, t) = rmqBuild (map (read :: String -> Int) (words (ds !! 1)))
      qs = map (\x -> map (read :: String -> Int) (words x)) (drop 2 ds)
  mapM_ (\x -> putStrLn $ show (rmqQuery n t (x !! 0) ((x !! 1) + 1) :: Int))
        qs


{-| test input
10 5
10 20 30 40 11 22 33 44 15 5
0 5
1 2
8 9
0 9
4 6
-}