RedHotChiliPepper

SegTree minimum .hs

Nov 29th, 2021
840
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. data SegTree a b = Empty |
  2.                SegTree { subtL :: SegTree a b
  3.                        , segL :: a
  4.                        , segR :: a
  5.                        , valOnSeg :: b
  6.                        , subtR :: SegTree a b
  7.                        } deriving Show
  8.  
  9. intINF = maxBound::Int
  10.  
  11. getVal :: SegTree a Int -> Int
  12. getVal Empty = intINF
  13. getVal tree = valOnSeg tree
  14.  
  15. buildSegTree :: Int -> Int -> UArray Int Int -> SegTree Int Int
  16. buildSegTree l r arr
  17.   | l+1==r = SegTree Empty l r (arr!l) Empty
  18.   | otherwise = SegTree left l r (min (getVal left) (getVal right)) right
  19.     where mid = (l + r) `div` 2
  20.           left = buildSegTree l mid arr
  21.           right = buildSegTree mid r arr
  22.  
  23. getMin :: Int -> Int -> SegTree Int Int -> Int
  24. getMin l r Empty = intINF
  25. getMin l r (SegTree subtl tl tr mn subtr)
  26.   | tl >= r || tr <= l = intINF
  27.   | l <= tl && tr <= r = mn
  28.   | otherwise = min (getMin l r subtl) (getMin l r subtr)
  29.     where mid = (tl+tr) `div` 2
RAW Paste Data