# Space efficient data structure for subsets of [1:n]

Let $S= \{1,2,3...,n\}$ be a set and I want to store a subset of $A \subseteq S$. Is there exists any data structure such that insert$(x)$, delete ($x$) can be done in amortised $O(1)$ time and search($x$) can be done in $O(1)$ time, where $x\in A$. Space used by data structure should be $O(n \log^{*}n)$ or $O(n)$ bits. Model of computation is RAM.

A bit vector $B$ can also be compressed in order to achieve $$O(nH_0(B)) \text{ bits}$$ of space. Depending on the distribution of 0's and 1's, this could be $o(n)$ bits.