作者 Anonymous [actionscript] 2012-01-19 12:47 (点击下载)

data SegTr a = Null
  | Bin {
    l :: Int,
    r :: Int,
    s :: a,
    lt :: SegTr a,
    rt :: SegTr a
  } deriving (Show)
 
build xs = build' 0 (length xs - 1)
  where
    build' l r
      | l == r = Bin l l (xs !! l) Null Null
      | otherwise = Bin l r sum lt rt
        where
          m = (l + r) `div` 2
          lt = build' l m
          rt = build' (m + 1) r
          sum = s lt + s rt
 
segAdd t @ (Bin l r sum lt rt) l1 r1 x
  | (r1 < l) || (r < l1) = t
  | l == r = Bin l l (sum + x) lt rt
  | otherwise = Bin l r sum' lt' rt'
    where
      sum' = sum + (r - l + 1) * x
      lt' = segAdd lt l1 r1 x
      rt' = segAdd rt l1 r1 x
 
segAns t @ (Bin l r sum lt rt) l1 r1
  | (r1 < l) || (r < l1) = 0
  | l == r = sum
  | otherwise = segAns lt l1 r1 + segAns rt l1 r1