module Data.SegmentTree.Examples
(
intervalSum
, intervalAny
, GCD(..), intervalGCD
, intervalConcat
, Unwords(..), intervalUnwords
) where
import Data.SegmentTree
import Data.Monoid
intervalSum :: SegmentTree (Sum Int) -> (Int, Int) -> Int
intervalSum t bds@(l, u) = getSum $ queryTree t bds
intervalAny :: SegmentTree Any -> (Int, Int) -> Bool
intervalAny t bds@(l, u) = getAny $ queryTree t bds
newtype (Integral a) => GCD a = GCD { getGCD :: a }
instance (Integral a) => Monoid (GCD a) where
mempty = GCD $ fromIntegral 1
(GCD x) `mappend` (GCD y) = GCD $ gcd x y
intervalGCD :: SegmentTree (GCD Int) -> (Int, Int) -> Int
intervalGCD t bds@(l, u) = getGCD $ queryTree t bds
intervalConcat :: SegmentTree String -> (Int, Int) -> String
intervalConcat t bds@(l, u) = queryTree t bds
newtype Unwords = Unwords { getUnwords :: String }
instance Monoid Unwords where
mempty = Unwords ""
(Unwords "") `mappend` y = y
x `mappend` (Unwords "") = x
(Unwords x) `mappend` (Unwords y) = Unwords (x ++ " " ++ y)
intervalUnwords :: SegmentTree Unwords -> (Int, Int) -> String
intervalUnwords t bds@(l, u) = getUnwords $ queryTree t bds