The `MkTreapAugDict` functor

« 210 Library Documentation

Overview

functor MkTreapAugDict
(structure Key : ORDKEY
 type value
 val combine : value * value → value
 val identity : value)
:> AUG_SORTED_DICT where Key = Key and type value = value and Seq = ArraySequence

Implements augmented sorted dictionaries as treaps, built with MkAugTreap.

`AUG_SORTED_DICT` Cost Specifications

Assuming that combine takes constant work and span, every operation shared with SORTED_DICT has the cost given for MkTreapDict. In addition:

	Work	Span
`reducedVal` $d$	\[O(1)\]	\[O(1)\]