Data.SegmentTree

This module contains the SegmentTree data structure, its constructor and the query function.

Example Usage:

     import Data.Monoid
     import Data.SegmentTree
     ...
     st = mkTree $ map Sum [0..10]
     ...
     queryTree st (0, 10) == Sum 55
     queryTree st (5, 10) == Sum 45
     queryTree st (0, 4)  == Sum 10

Documentation

data Monoid a => SegmentTree a

A SegmentTree is a binary tree and the bounds of its corresponding interval.

Constructors

SegmentTree (Tree a) (Int, Int)

Instances

Monoid a => Show (SegmentTree a)

mkTree :: Monoid a => [a] -> SegmentTree a

Build the SegmentTree for the given list. Time: O(n*log n)

queryTree :: Monoid a => SegmentTree a -> (Int, Int) -> a

Query the SegmentTree for the specified closed interval. Time: O(log n)