A pista para encontrar a estrutura de dados correta aqui é que os requisitos ( além dos requisitos de espaço e acessibilidade direta ) são os de uma árvore binária. Isso me fez pensar em como você poderia modificar uma árvore binária para que ela atendesse aos requisitos.
O que você pode fazer é serializar efetivamente em uma matriz uma passagem de pré-ordem de largura de uma árvore binária que armazena 1 ou 0 para a presença de cada item no conjunto, ou para nós não-folha a presença de qualquer um dos nós filhos. A inserção então requer que os bits O (log n) sejam definidos como 1, a exclusão requer que os bits O (log n) sejam copiados de um nó could, e o máximo é uma busca binária. O acesso direto ainda é possível porque os nós folha têm o mesmo formato que o vetor de bits, ignorando os primeiros (n-1) bits.
Exemplo: n = 8, com itens 2, 3, 4 e 6 definidos:
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.