We introduce a data structure for representing a partition of an integer n, which uses O(n)~1/2 bits of space. This is constant multiple of the information theoretic lower bound. Three types of operations accesS_p, bound_p, prefixsum_p are supported in constant time by using the notion of conjugate of a partition. In order to construct this data structure, we also construct a data structure for representing a monotonic sequence, which supports the same operations in constant time and uses O(min{1/δu(n/u)~δ , 1/δn (u/n)~δ }) bits of space for any positive constant 5. (n is the number of terms, and u denotes the size of the universe.)
展开▼
