zagadka algorytmiczna

W sumie znam jedną zagadkę algorytmiczną ;> Za to bardzo ją lubię (i pewnie dla tego ją pamiętam):

Generalnie pytanie brzmi: jak używać niezainicjalizowanej tablicy?

Zakładamy, że alokacja bloku pamięci wykonuje się w czasie stałym, czyli O(1) i czas alokacji pojedynczego bloku nie jest zależy od wielkości bloku pamięci.

Zadanie:
Znajdź algorytm, który pozwoli korzystać z niezainicjalizowanej tablicy.
Tworzenie tej tablicy ma się odbywać w czasie STAŁYM (czyli nie możemy sobie pozwolić na np. wyzerowanie jej wszystkich elementów; tablica - po zaalokowaniu - wypełniona jest śmieciami).
Dostęp (odczyt / zapis) do i-tego elementu ma się odbywać w czasie O(1), czyli tak jak w normalnej tablicy.
Naturalnie można korzystać z pomocniczych struktur ;)
Można założyć, że operacja odczytu i-tego elementu, który wcześniej nie był zapisywany, ma zwracać 0.

(koniec zagadki)

I żeby rozwiać wszelkie wątpliwości jeszcze mój komentarz:
Dla "normalnych" tablic, mamy tak (n - ilość elementów):
złożoność pamięciowa: O(n)
złożoność czasowa tworzenia i inicjalizacji tablicy: O(n)
operacja odczytu i-tego elementu: O(1)
operacja zapisu i-tego elementu: O(1)

Celem zagadki, jest znalezienie struktury danych, o takich samych charakterystykach, z tą różnicą, że czas tworzenia (i ewentualnej inicjalizacji) ma być: O(1).

Bez straty ogólności można założyć, że w tablicy mamy liczby typu int.