Succinct dynamic dictionaries and trees

Abstract. We consider space-efficient solutions to two dynamic data structuring problems. We first give a representation of a set S ⊆ U = {0,...,m − 1}, |S | = n that supports membership queries in O(1) worst case time and insertions into/deletions from S in O(1) expected amor-tised time. The representation uses B+ o(B) bits, where B = l