adaptive radix trie can be and is used for sparse arrays, O(log(k)) where k is the key size, const for bounded integers alternatively, depending on your data

adaptive radix trie can be and is used for sparse arrays, O(log(k)) where k is the key size, const for bounded integers alternatively, depending on your data and the sparseness, bit vectors can indicate filled and empty slots and popcnt be used to find the actual slot for some index.