The clue to finding the right data structure here is that the requirements (other than the space requirements and direct accessibility) are those of a binary tree. This got me thinking about how you could modify a binary tree to make it meet the requirements.
What you can do is to effectively serialise into an array a pre-order breadth-first traversal of a binary tree that stores a 1 or 0 for presence of each item in the set, or for non-leaf nodes the presence of any of the child nodes. Insertion then requires O(log n) bits to be set to 1, deletion requires O(log n) bits to be copied from a could node, and maximum is a binary search. Direct access is still possible because the leaf nodes have the same format as the bit vector, ignoring the first (n-1) bits.
Example: n = 8, with items 2, 3, 4 and 6 set:
1 11 1110 01110100
^ root: some values are in the set
^^ second level: values present in both first and second halves
^^^^ third level: quarters 1,2, and 3 have members, but the final quarter is empty
^^^^^^^^ leaves, essentially the same as the bit vector described in the question.