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.
Bit vectors fulfill all your requirements.