Design an efficient data structure for representing a subset S of the integers from 1 to n. The operations we wish to perform are these:

1) Select an integer i from the set and delete it.

2) Add an integer i to the set.

A mechanism must be provided to ignore a request to add integer i to S in the case where S alrady contains i. The data structure must be such that the time to select and delete an element and the time to add an element are constant and not dependent on ||S||, the size of S.

Analyze the time and space complexity of your algorithms.